e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Euclid Problem

Euclid Problem

From Euclid it is known that for any positive integers a and b there exist such integers x and y that ax + by = d, where d is the greatest common divisor of a and b. The problem is to find for given a and b corresponding x, y and d.

Input

Each line contains two positive integers a and b (a, b109).

Output

For each test case print in a separate line three integers x, y and d, separated by space. If there are several such x and y, print the pair for which |x| + |y| is minimal. If there also exist multiple answers, print the pair with minimum value of x.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 6
17 17
5 3
Output example #1
-1 1 2
0 1 17
-1 2 1