Description

Sheng bill 有着惊人的心算能力, 甚至能用大脑计算出两个巨大的数的 GCD (最大公约数)! 因此他经常和别人比赛计算 GCD. 有一天 Sheng bill 很嚣张地找到了你, 并要求和你比赛, 但是输给 Sheng bill 岂不是很丢脸! 所以你决定写一个程序来教训他.

Input

共两行: 第一行: 一个数 \(A\). 第二行: 一个数 \(B\).

Output

一行, 表示 \(A\) 和 \(B\) 的最大公约数.

Sample Input

12
54

Sample Output

6

Data Range

对于 20% 的数据,\(0 \lt A, B \leq 10^{18}\);

对于 100% 的数据,\(0 \lt A, B \leq 10^{10000}\).

Explanation

Python 大法好~

话说有的人写 C++写得比 Python 还慢是什么鬼......

Source Code


a = int(input())
b = int(input())
c = a % b
while c > 0:
    a = b
    b = c
    c = a % b
print(b)