Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.
Входные данные: Вводятся три натуральных числа.
Выходные данные: Выведите ответ на задачу.
Примечание
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 2 3 |
1 1 |
| 2 |
10 6 8 |
2 -2 |
Prohibited statements:gcd