e-olymp
Competitions

Azerbaijan Programming Olympiad - 2nd Stage preparation

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.

Input

Each line contains two positive integers a and b, separated by space (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.

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