Description

给定两个正整数 \(a\) 和 \(b\)，求出它们的最大公约数。
\(0<a,b<=2^{31}-1\)

Input

一行，两个正整数 \(a\) 和 \(b\)。

Output

一行，一个正整数，表示它们的最大公约数

Sample Input

12 18

Sameple Output

6

特别要求

请用递归和非递归各实现一遍