Greatest Common Divisor

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given nonnegative a,b, not both zero, compute their greatest common divisor.

Input

One line contains two integers a,b.

Output

Print their gcd as one integer.

Subtasks

• Subtask 1 (20%): 0≤a,b≤100, a+b>0.
• Subtask 2 (30%): 0≤a,b≤1000000000, a+b>0.
• Subtask 3 (50%): 0≤a,b≤10^18, a+b>0.

Examples

Example 1

Input

0 18

Output

18

Explanation

gcd(0,18) equals 18; one modulo step reaches (18,0).

Example 2

Input

30 18

Output

6

Explanation

The Euclidean sequence ends at six.