Euclid by Repeated Subtraction

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given positive a and b, find their greatest common divisor by repeatedly subtracting the smaller from the larger.

Input

One line with two positive integers a,b.

Output

Print gcd(a,b).

Subtasks

• Subtask 1 (20%): 1 ≤ a,b ≤ 100.
• Subtask 2 (30%): 1 ≤ a,b ≤ 1000.
• Subtask 3 (50%): 1 ≤ a,b ≤ 10000.

Examples

Example 1

Input

18 30

Output

6

Explanation

Repeated subtraction gives (18,30), (18,12), (6,12), (6,6).

Example 2

Input

7 7

Output

7

Explanation

The two numbers are already equal.