题目描述

给定三个整数 $a$、$b$、$k$（$1 \leq a,b \leq 10^9$，$0 \leq k \leq 10^{18}$），请判断是否存在非负整数 $x$ 和 $y$，使得等式 $a \times x + b \times y = k$ 成立。若存在，输出任意一组合法的 $x$ 和 $y$；若不存在，输出 $-1$。

输入格式

一行包含三个整数 $a$、$b$、$k$，整数之间用空格分隔。

输出格式

若存在合法解，输出两个非负整数 $x$ 和 $y$；否则输出 $-1$。

样例输入 1

3 5 7

样例输出 1

-1

样例输入 2

2 4 5

样例输出 2

-1

样例输入 3

5 3 0

样例输出 3

0 0

数据范围

• $1 \leq a, b \leq 10^9$
• $0 \leq k \leq 10^{18}$

测试点$1 - 5$ 边界$k=0$

测试点$6 - 10$ 边界$a=1$

测试点$11 - 15$ 无解（$k$不是$gcd$倍数）

测试点$16 - 20$ 无解（$k$是$gcd$倍数但无非负解）

测试点$21 - 40$ 有解