Problem A
Extended GCD

Implement an algorithm to find the greatest common divisor of two integers $a$ and $b$, often denoted by $\gcd (a,b)$.

Input

Input is two lines. The fyrst line contains the integer $a$. The second line contains the integer $b$.

Output

Output three lines. The first line should contain the integer $g$, where $g=\gcd (a,b)$ and $g=ua+vb$. The second line should contain the integer $u$. The third line should contain the integer $v$.

Scoring

6
15

3
-2
1

4
0

4
1
0

6
15

3
3
-1