Thuật toán Euclid tìm ước chung lớn nhất: ~\gcd(a, b) = \gcd(b, a \bmod b)~ và ~\gcd(a, 0) = a~. Hãy cài đặt hàm đệ quy theo công thức này để tìm UCLN của hai số ~a, b~.

Dữ liệu vào

Một dòng gồm hai số nguyên dương ~a, b~ cách nhau bởi dấu cách (~1 \le a, b \le 10^{18}~).

Kết quả

In ra UCLN của ~a~ và ~b~.

Ví dụ

Ví dụ 1

Input:

12 18

Output:

6

Ví dụ 2

Input:

17 5

Output:

1

Giải thích

~\gcd(12, 18) = \gcd(18, 12) = \gcd(12, 6) = \gcd(6, 0) = 6~.