Azerbaijan Programming Olympiad - 2nd Stage preparation
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, separated by space (a, b ≤109).
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.
4 6 17 17 5 3
-1 1 2 0 1 17 -1 2 1