Задача G. Диофантово уравнение

Автор:Известная   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Для заданных чисел a, b, c решить диофантово уравнение ax + by = c в целых числах

Формат входных данных

Три целых числа a, b, c, разделенные пробелами

Формат выходных данных

Вывести пару целых чисел (x, y) - решение заданного диофантова уравнения, в котором x минимально возможный неотрицательный. Если таких пар несколько, выведите пару с минимальным неотрицательным y

В случае, если решений не существует, вывести -1

Ограничения

 − 231 < a, b, c < 231

Примеры тестов

Стандартный вход Стандартный выход
1
2 3 1
2 -1
2
6 4 3
-1
3
0 2 6
0 3

0.072s 0.009s 13