Thuật toán Euclid tìm ước chung lớn nhất (UCLN) của hai số nguyên \(A\) và \(B\) là một trong những thuật toán đệ quy cổ xưa và đẹp đẽ nhất trong lịch sử nhân loại. Công thức đệ quy dựa trên tính chất: \(\gcd(A, B) = \gcd(B, A \bmod B)\) với trường hợp cơ sở \(\gcd(A, 0) = A\). Hãy lập trình giải bài toán này.

Định dạng đầu vào

• Một dòng duy nhất chứa hai số nguyên dương \(A, B\) (\(1 \le A, B \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là ước chung lớn nhất của \(A\) và \(B\).

Ví dụ

Input:

12 18

Output:

6