Chứng chỉ Bézout chuẩn hóa

Bối cảnh và bài toán

Một hệ thống kiểm chứng cần sinh "chứng chỉ Bézout" cho nhiều cặp số nguyên dương. Với mỗi cặp (a,b), chứng chỉ gồm ba số (x,y,d) sao cho d=gcd(a,b) và a*x+b*y=d.

Để các node khác nhau luôn xuất đúng cùng một chứng chỉ, hệ thống chuẩn hóa x về khoảng 0 <= x < b/d; y sau đó được xác định duy nhất.

Yêu cầu

Với mỗi cặp (a,b), hãy in bộ (x,y,d) thỏa a*x+b*y=d=gcd(a,b) và 0 <= x < b/d.

Input

• Dòng 1: số nguyên q.
• q dòng tiếp theo: mỗi dòng chứa hai số nguyên dương a b.

Output

Với mỗi truy vấn, in x y d theo chuẩn của đề.

Ràng buộc

• 1 <= q <= 10^5
• 1 <= a,b <= 10^9

Chấm điểm

Ví dụ 1

Input

2
4 6
17 17

Output

2 -1 2
0 1 17

Giải thích. Với 4,6, d=2, khoảng chuẩn của x là [0,2]; x=2 cho 4*2+6*(-1)=2. Với 17,17, b/d=1 nên x=0.

Ví dụ 2

Input

2
35 12
10 6

Output

11 -32 1
2 -3 2

Giải thích. Các hệ số được chuẩn hóa theo khoảng đã nêu, nên output là duy nhất.

Thông tin bài tập

Nguồn: Phỏng theo UVa Online Judge 10104 — Euclid Problem. Tham khảo: https://onlinejudge.org/external/101/10104.pdf