Ước chung lớn nhất đệ quy

Cho hai số nguyên dương \(a\) và \(b\). Hãy viết hàm đệ quy tìm ước chung lớn nhất (gcd) của chúng, chẳng hạn dựa trên thuật toán Euclid: \(\gcd(a, 0) = a\) và \(\gcd(a, b) = \gcd(b, a \bmod b)\).

Input

Một dòng gồm hai số nguyên dương \(a\) và \(b\).

Output

In ra ước chung lớn nhất của \(a\) và \(b\).

Constraints

• \(1 \le a, b \le 10^{18}\)

Sample Input 1

84 36

Sample Output 1

12

Sample Input 2

100 75

Sample Output 2

25