Competitions

# Azerbaijan Programming Olympiad - 2nd Stage preparation

# Euclid Problem

From Euclid it is known that for any positive integers ** a** and

**there exist such integers**

*b***and**

*x***that**

*y**, where*

**ax**+**by**=**d****is the greatest common divisor of**

*d***and**

*a***. The problem is to find for given**

*b***and**

*a***corresponding**

*b***,**

*x***and**

*y***.**

*d***Input**

Each line contains two positive integers ** a** and

**, separated by space (**

*b**≤*

**a**,**b***).*

**10**^{9}**Output**

For each test case print in a separate line three integers * x, y* and

*separated by space. If there are several such*

**d**,**and**

*x***, print the pair for which**

*y**|*is minimal. If there also exist multiple answers, print the pair with minimum value of

**x**| + |**y**|**x**.

Input example #1

4 6 17 17 5 3

Output example #1

-1 1 2 0 1 17 -1 2 1