Extended Euclid's Algorithm

Plus

Problem description Progress

ID 31903. Extended Euclid's Algorithm

Natural numbers are given \(a, b, c.\) If the equation is \(a \cdot x + b \cdot y = c\) has integer solutions, then print \(gcd(a,b)\), \(x\) and \(y\) (any solution). If there is no solution, then print the word Impossible.

Input data
Natural numbers and do not exceed 10000 in absolute value.

Imprint
Print the answer to the problem.

Examples

#	Input	Output
1	1 2 3	1 1 1
2	10 6 8	2 2 -2

ID 33656. Diophantine equations

Темы: Extended Euclid's Algorithm

Natural numbers a, b, c are given. If the equation \(ax+by=c\) has solutions in integers, then choose the solution in which the number x has the smallest non-negative value and output this solution (two numbers x and y separated one space). If there is no solution, then print the word Impossible.

Input
Three natural numbers are entered.

Imprint
Print the answer to the problem.

Note
The complexity of the algorithm must be equal to the complexity of the Euclidean algorithm + a constant.

Examples

#	Input	Output
1	1 2 3	1 1
2	10 6 8	2 -2