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

Ràng buộc & Subtasks