← 返回题目列表

Codeforces · 946/B

B. 奇怪的减法过程

中文机器翻译题面 查看原题

你有两个变量 a 和 b。考虑使用这些变量执行以下操作序列:

1. 如果a = 0或b = 0,则结束该过程。否则转步骤2;
2、若a ≥ 2·b,则将a的值设置为a - 2·b,重复步骤1,否则转步骤3;
3、如果b ≥ 2·a,则将b的值设置为b - 2·a,并重复步骤1。否则,结束该过程。

最初,a 和 b 的值是正整数,因此该过程将是有限的。

进程结束后,您必须确定 a 和 b 的值。

输入

输入的唯一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1018)。 n是变量a的初始值,m是变量b的初始值。

输出

打印两个整数 — 进程结束后 a 和 b 的值。

示例

输入 #1

12 5

输出 #1

0 1

输入 #2

31 12

输出 #2

7 12

注意

样本说明:

1. a = 12,b = 5 $$\rightarrow$$ a = 2,b = 5 $$\rightarrow$$ a = 2,b = 1 $$\rightarrow$$ a = 0,b = 1;
2. a = 31,b = 12 $$\rightarrow$$ a = 7,b = 12。