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