Extended Euclidean 2

Problem Description

Read $T$; there are $T$ groups of data. Each group gives three numbers $a, b, d$; output a non-negative integer solution $(x, y)$ of $ax+by=d$. If there is no solution, output $-1$; otherwise output the solution with the smallest $x$.

Input Format

The first line contains one number $T$.

The following $T$ lines each contain three numbers $a, b, d$.

Output Format

$T$ lines in total, each with two numbers: $x, y$.

Sample Input

3
1 2 5
100 150 1000
3 2 1

Sample Output

1 2
1 6
-1

Constraints

For $100\%$ of the data, it is guaranteed that $1\leq T\leq 10^4$, $1\leq a, b\leq 10^9$, $1\leq d\leq 10^{18}$.

Hint

• Use the extended Euclidean algorithm to solve $ax+by=\gcd(a,b)$. A solution to $ax+by=d$ exists iff $\gcd(a,b)\mid d$. To get the smallest non-negative $x$, first find one solution then shift by multiples of $b/\gcd$ (and $a/\gcd$ for $y$).