Hide

Problem A
Extended GCD

Languages en is

Implement an algorithm to find the greatest common divisor of two integers $a$ and $b$, often denoted by $\mathrm{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 = \mathrm{gcd}(a, b)$ and $g = ua + vb$. The second line should contain the integer $u$. The third line should contain the integer $v$.

Scoring

Group

Points

Constraints

1

60

$1 \leq a, b \leq 10^{18}$.

2

20

$0 \leq a, b \leq 10^{18}$.

3

20

$0 \leq a, b \leq 10^{18}$, $u > 0$ and $u$ should be minimized.

Sample Input 1 Sample Output 1
6
15
3
-2
1
Sample Input 2 Sample Output 2
4
0
4
1
0
Sample Input 3 Sample Output 3
6
15
3
3
-1