Codeforces Beta Round #7 C. Line

Codeforces Beta Round #7 C. Line

题目链接

A line on the plane is described by an equation Ax + By + C = 0. You are to find any point on this line, whose coordinates are integer numbers from  - 5·1018 to 5·1018 inclusive, or to find out that such points do not exist.

Input

The first line contains three integers A, B and C ( - 2e9 ≤ A, B, C ≤ 2e9) — corresponding coefficients of the line equation. It is guaranteed that $A^2+B^2>0$.

Output

If the required point exists, output its coordinates, otherwise output -1.

Examples

input

2 5 3
1

output

6 -3
1

拓展欧几里得模板题，求 $ax+by=-c$ 的一组解即可，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll X,Y;
void Gcd(ll A,ll B,ll &gcd)
{
	if(B){Gcd(B,A%B,gcd);ll t=X;X=Y;Y=t-(A/B)*Y;}
	else {gcd=A;X=1,Y=0;}
}
void exgcd(ll A,ll B,ll C){
    ll gcd;
    Gcd(A,B,gcd);
    if(C%gcd) printf("-1\n");
    else{
        X*=C/gcd;
        Y*=C/gcd;
        printf("%lld %lld\n",X,Y);
    }
}

int main(){
   ll a,b,c,d;
    cin>>a>>b>>c;
    c=-c;
    exgcd(a,b,c);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26