12012 - 求解方程

给定一个线性方程 ax + by = c ,其中 a, b, c 均为自然数(正整数),请求出该方程的所有正整数解(即 x > 0 , y > 0 ),并按照 x 从小到大的顺序输出每个解。

如果没有正整数解,则输出 -1

输入

输入只有一行,包含三个整数 a, b, c ,之间用空格隔开。

输出

若存在正整数解,则输出若干行,每行包含两个整数 xy ,表示一组解, x 在前, y 在后,中间用一个空格隔开。所有解按照 x 的值从小到大输出。

若不存在正整数解,则输出一行 -1

样例

输入

3 5 100

输出

5 17
10 14
15 11
20 8
25 5
30 2

提示

数据范围

  • 0 < a, b, c \le 10^5
  • 0 < x \le 3000
  • 0 < y \le 2000
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题