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\le \sqrt{k}$.

Input

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

Output

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

73 27 73

8 3