Extended Euclidean Algorithm

medium
Question Solve Solutions 
You have been given two Integers a and b. you need to find an integral solution of x and y such that a*x + b*y= gcd(a,b).
It can be proven that solution always exist.

Input Format

The first line contains 2 integer a and b

Output Format

output integral value of x and y in a single line.

Constraints

1 <= a, b <= 10^6

Example

Input
34
24
Output
5 -7
Next
Linear Diophantine Equation

Related Questions

medium Linear Diophantine Equation hard Eulers Totient Function medium Wilsons Theorem medium Modular Fast Exponentiation medium Modular C(n,r) hard No Max No Min medium Prime Factors Using Sieve medium All Factors Using Sieve easy Count Of Common Divisors medium Gcd Length medium I Hate 1111 medium Relatively Prime Pairs medium Sum Of Factors easy Chinese Remainder Theorem easy Monkey Tradition