This page is still under construction.

Parts of this page are still being built. What you see may change.

Ax+By=C

Time limit1sMemory limit1024 MB

Summary

Given integers A, B, C, find integer x and y with Ax + By = C within plus or minus one billion, or report that none exists.

Level: Medium7 of 10
Topics: Math, Number theory, Implementation, Brute force
Solved: No attempts yet

Problem

Given A, B, and C, find any pair (x, y) that satisfies Ax+By=C and the following conditions.

x and y are integers
-1,000,000,000 ≤ x, y ≤ 1,000,000,000

Input

The first line contains the integers A, B, and C.

Output

Print x and y satisfying Ax+By=C, separated by a space. If no (x, y) satisfies the conditions of the problem, print -1.

Constraints

-1,000,000 ≤ A, B, C ≤ 1,000,000
A, B ≠ 0

Examples3

Example 1
Input
```
1 2 3
```
Expected output
```
3 0
```
Example 2
Input
```
3 4 5
```
Expected output
```
-5 5
```
Example 3
Input
```
6 8 3
```
Expected output
```
-1
```

Loading...