Задача Евкліда

Ще з часів Евкліда відомо, що для довільних натуральних чисел $a$ та $b$ завжди існують такі цілі $x$ та $y$, що $a\cdot x+b\cdot y=d$, де $d$ — найбільший спільний дільник $a$ та $b$. В цій задачі за заданими $a$ та $b$ слід знайти відповідні $x,y$ та $d$.

Вхідні дані

Кожний рядок містить два натуральні числа $a$ та $b(a,b\le 10^9)$.

Вихідні дані

Для кожногї пари $a$ та $b$ в окремому рядку вивести три цілі числа $x,y$ та $d$, розділені пропуском. Якщо шуканих значень $x$ та $y$ декілька, то слід вивести таку пару, для якої значення $|x|+|y|$ найменше. Якщо і таких пар декілька, то вивести ту пару, в якій $x$ мінімальне.

Приклади