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

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.


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


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