時間制限 : sec, メモリ制限 : KB
English / Japanese  

拡張ユークリッドの互除法

与えられた2つの整数 ab について ax + by = gcd(a, b) の整数解 (x, y) を求めてください。ここで、gcd(a, b)ab の最大公約数です。

入力

a b

2つの整数 ab が1つの空白区切りで1行に与えられる。

出力

xy を1つの空白区切りで1行に出力する。ただし、そのような組が複数ある場合は、|x| + |y| が最小のものを出力する。最小のものが複数ある場合はその中で xy であるものを出力する。

制約

  • 1 ≤ a, b ≤ 109

入力例 1

4 12

出力例 1

1 0

入力例 2

3 8

出力例 2

3 -1