Euclid Problem

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$.

Input

Each line contains two positive integers $a$ and $b(a,b\le 10^9)$.

Output

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$.

Examples