Teaching Sheng Bill a Lesson: Compute the GCD

Sheng Bill is known for his astonishing mental calculation ability, even capable of determining the greatest common divisor (GCD) of two huge numbers in his head! One day, he arrogantly challenged you to a GCD contest. Losing to him would be humiliating, so you decide to write a program to teach him a lesson.

Your task is to compute the greatest common divisor (GCD) of two given positive integers. You can recall the famous Euclidean algorithm: $$\gcd(a, b) = \gcd(b, a \mod b)$$ with the base case \(\gcd(a, 0) = a\).

Input numbers will be large but guaranteed to be within the range of 64-bit integers.

inputFormat

The input consists of a single line containing two positive integers a and b (1 ≤ a, b ≤ 10¹⁸) separated by a space.

outputFormat

Output a single integer, the greatest common divisor of a and b.

sample

10 5

5