#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Euclidean Algorithm - Classic Problems | Repovive

CLS8. Euclidean Algorithm

1s256 MB

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both.

Given two integers $a$ and $b$ , compute $\gcd(a, b)$ .

Note: $\gcd(0, n) = \gcd(n, 0) = n$ for any positive $n$ .

Constraints

$0 \le a, b \le 10^{18}$
At least one of $a$ or $b$ is positive

Input

$a \quad b$

Output

$\gcd(a, b)$

Samples

Input

12 8

Explanation

For this input, the required output is 4.

Output

Input

17 13

Explanation

For this input, the required output is 1.

Output

Input

100 25

Explanation

For this input, the required output is 25.

Output

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both.

Given two integers $a$ and $b$ , compute $\gcd(a, b)$ .

Note: $\gcd(0, n) = \gcd(n, 0) = n$ for any positive $n$ .

$0 \le a, b \le 10^{18}$
At least one of $a$ or $b$ is positive

$a \quad b$

$\gcd(a, b)$