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

Со времен Евклида известно, что для любых натуральных чисел $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$ минимально.

Примеры