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 |
Запрещенные операторы:gcd