B. Расширенный Евклид

По числам $a$ и $b$ найдите их наибольший общий делитель $g$ и такие целые $x$ и $y$, что $ax + by = g$.

Два числа $a$ и $b$ ($1 \le a, b \le 10^{18}$).

Выведите три числа: $g$, $x$ и $y$, где $g = \gcd(a, b)$ и $ax + by = g$.

Среди всех пар выберите ту, где $x$ наименьший неотрицательный.