From Euclid it is known that for any positive integers a and b there exist such integers x and y that a⋅x+b⋅y=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,b≤109).
For each test case print in a separate line three integers x,y and d. 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.