Задача Евкліда#1155
З курсу Евкліда відомо, що для будь-яких додатних цілих чисел і існують цілі числа і такі, що a \cdot x + b \cdot y = d, де — це найбільший спільний дільник чисел і .
Дано і . Знайдіть такі цілі числа , та .
У кожному рядку знаходяться два додатних цілих числа і (a, b \le 10^9).
Для кожної пари і виведіть три цілі числа , і , розділені пробілами в одному рядку. Якщо існує декілька таких пар, виведіть ту, для якої |x| + |y| мінімальне. Якщо і тут є декілька розв’язків, виведіть той, в якому мінімальний.
Приклад 1