p02471 Extended Euclid Algorithm
Extended Euclid Algorithm




Given positive integers a and b, find the integer solution (x, y) to ax + by = gcd(a, b), where gcd(a, b) is the greatest common divisor of a and b.

Constraints

* 1 ≤ a, b ≤ 109

Input


a b


Two positive integers a and b are given separated by a space in a line.

Output

Print two integers x and y separated by a space. If there are several pairs of such x and y, print that pair for which |x| + |y| is the minimal (primarily) and x ≤ y (secondarily).

Examples

Input

4 12


Output

1 0


Input

3 8


Output

3 -1
```python
import sys
sys.setrecursionlimit(10 ** 7)

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

a, b = map(int, input().split())


def extgcd(a, b):
    if b == 0:
        return a, 1, 0

    p, q = a // b, a % b
    d, x, y = extgcd(b, q)
    x, y = y, x - p * y
    return d, x, y


reverse = False
if b > a:
    a, b = b, a
    reverse = True

d, x, y = extgcd(a, b)

if reverse:
    x, y = y, x

print(x, y)


```