题目描述

给定两个正整数 $a, b$，请使用扩展欧几里得算法求出一组整数 $x, y$，使得

并输出 $\gcd(a, b)$ 以及这组解 $(x, y)$。

本题任何一组满足方程的整数解 $(x, y)$ 都算正确，不要求唯一。

输入格式

一行，两个整数 $a, b$（$1 \le a, b \le 10^9$）。

输出格式

一行，三个整数 $g \; x \; y$，分别表示 $\gcd(a, b)$、以及满足方程的一组解 $x, y$。

样例

30 20

10 1 -1

（验证：$30 \times 1 + 20 \times (-1) = 10 = \gcd(30, 20)$）

说明/提示

普通欧几里得算法只能求最大公约数；扩展欧几里得算法在递归求 $\gcd$ 的过程中回溯，同时得到系数 $x, y$，满足 $a x + b y = \gcd(a, b)$。本题使用特判验证，因此任何正确的 $(x, y)$ 都会被接受。