Буратино решил похвастаться своими успехами в математике перед котом Базилио и лисой Алисой.
Кот Базилио был потомком "кота ученого" поэтому знал некоторые секреты математики.
Лиса Алиса сказала Буратино, что в "стране Дураков" можно добыть быстрый алгоритм нахождения НОД (см. теорию), а кот Базилио показал несколько решений.
Попробуйте, используя примеры, написать программу, которая будет выводить аналогичные решения.
Входные данные : Числа
A,
B (числа записаны в две строки, каждое не более 1000000000). Гарантируется, что
A не равно
B.
Выходные данные: Промежуточные результаты вычислений (набор строк, в каждой по два числа). В последней стороке одно число - НОД
Примечание :
Первая строка содержит начальное состояние (1-е число, 2-е число)
Последняя строка содержит одно число - значение НОД
48
72 |
48 72
48 24
0 24
24 |
33
45 |
33 45
33 12
9 12
9 3
0 3
3 |
126
35 |
126 35
21 35
21 14
7 14
7 0
7 |