From Euclid it is known that for any positive integers $a$ and $b$ there exist such integers $x$ and $y$ that $a \cdot x + b \cdot y = 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$. \InputFile Each line contains two positive integers $a$ and $b~(a, b \le 10^9)$. \OutputFile For each test case print in a separate line three integers $x, y$ and $d$. 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$.