Điểm nguyên trên đường thẳng

Tìm một điểm nguyên trên đường thẳng $A \cdot x + B \cdot y + C = 0$ , hoặc báo không tồn tại. Bất kỳ cặp số nguyên nào thỏa phương trình đều được chấp nhận.

Input

Một dòng chứa $A, B, C$ .

Output

In $- 1$ hoặc một cặp $x$ $y$ hợp lệ.

Constraints

$∣ A ∣, ∣ B ∣, ∣ C ∣ \leq 2 \cdot 1 0^{9} .$
$A$ và $B$ không đồng thời bằng $0$ .

Scoring

Subtask $1$ ( $50%$ số điểm): các test từ $1$ đến $10$ , dùng miền dữ liệu nhỏ để có thể đối chiếu độc lập.
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung ngoài các ràng buộc đã nêu.

Example

Test 1

Input

6 9 -3

Output

-1 1

Giải thích: Cặp $(- 1, 1)$ cho $6 \cdot (- 1) + 9 \cdot 1 - 3 = 0$ nên là một điểm nguyên hợp lệ.

Lời giải tóm tắt

Ý tưởng: Phương trình đường thẳng tương đương A·x+B·y=-C. Đặt g=gcd(|A|,|B|). Nếu g không chia -C, không có điểm nguyên và ta in -1.
Ý tưởng: Nếu có, Euclid mở rộng tìm hệ số Bézout của |A|,|B|; hiệu chỉnh dấu theo A,B rồi nhân với (-C)/g để thu được một điểm nguyên. Checker chấp nhận bất kỳ điểm hợp lệ nào.
Ý tưởng: Độ phức tạp O(log max(|A|,|B|)).