Extended Euclid Algorithm

Problem Description

Cho 2 số nguyên dương A,B. Tìm hệ số x,y của phương trình Ax+By=gcd(A,B). Trong đó gcd(A,B) là ước chung lớn nhất của A và B.

Input Format

• 2 số nguyên dương A và B
• 1 ≤ A,B ≤ 10^9

Constraints

Không có ràng buộc thêm.

Output Format

In ra hệ số x,y của phương trình.

Sample

Sample Input 0

10 6

Sample Output 0

-1 2

Note

Phương trình: 10x + 6y = gcd(10,6) = 2 Với x = -1, y = 2 thì: 10(-1) + 62 = -10 + 12 = 2 = gcd(10,6)