Problem D
Early Termination

Is this...?

You are given non-negative integers $a, b, k$ and are to implement Euclid’s algorithm with inputs $a, b$ but terminate it as soon as $a, b \leq \sqrt{k}$.

Input

The first and only line of input contains non-negative integers $a, b, k \leq 10^{18}$ separated by a space. We also have $a, b \geq 1$.

Output

Print $a, b$ separated by a space after Euclid’s algorithm has been run until $a, b \leq \sqrt{k}$. Print the larger number first.

73 27 73

8 3