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, b ≤ 109).

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.