Euclid Problem#1155
From Euclid, it is known that for any positive integers and , there exist integers and such that a \cdot x + b \cdot y = d, where is the greatest common divisor of and .
Given and , find such integers , , and .
Each line contains two positive integers and (a, b \le 10^9).
For each input pair and , output three integers , , and separated by spaces on a single line. If there are multiple such pairs, output the one where |x| + |y| is minimized. If there are still multiple solutions, output the one with the smallest .
Example 1