using System.IO;
using System;
class Euclid
{
    static void Main()
    {
        Console.Write("Input 1: ");
        int x = Convert.ToInt32(Console.ReadLine());
        Console.Write("Input 2: ");
        int y = Convert.ToInt32(Console.ReadLine());
        while(x != y)
        {
            Console.WriteLine(X + "\t" + y);
            if(x > y)
                x -= y;
            else
                y -= x;
        }
        Console.WriteLine(x + "\t" + y);
        Console.WriteLine("GCD: {0}",x);
    }
}