Problems

# Euclid Problem

# 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** (**a**, **b** ≤ `10`

).^{9}

#### 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**.

Input example #1

4 6 17 17 5 3

Output example #1

-1 1 2 0 1 17 -1 2 1