/*
  Name:    euclidGCD.c
  Purpose: Determines the greatest common divisor of a collection of ordered pairs
  Author:  Bill Slough
  Date:    January 10, 2011

  Input:   a sequence of input lines of the form a b

  Output:  a sequence of output lines of the form

             a b d

	   where d = gcd(a, b)

  Notes:   We use the recursive formulation of finding the greatest common divisor.  
           See, for example,
               Cormen et al., "Intro. to Algorithms", Section 31.2 
           for a discussion of this algorithm.
*/

#include <stdio.h>

int Euclid(int a, int b);

int main() {
  int a, b;       /* A pair of input values */
  int d;          /* d = gcd(a, b) */
  
  while (scanf("%d %d", &a, &b) != EOF) {
    /* Process and output one pair */
    d = Euclid(a, b);
    printf("%d %d %d\n", a, b, d);
  }
  return 0;
}

int Euclid(int a, int b) {
  /* Find the greatest common divisor of a and b.  Assumes a, b are non-negative. */
  if (b == 0)
    return a;
  else
    return Euclid(b, a % b);
}