Hai Lịch Không Đồng Nguyên · canuc80k5402

Mỗi bộ dữ liệu cho hai điều kiện về số dư của cùng một số nguyên: $x mod n = a$ và $x mod m = b$ . Hai mô-đun có thể có ước chung.

Nếu không có số nguyên nào thỏa đồng thời hai điều kiện, hãy thông báo không có nghiệm. Nếu có, đặt $K = lcm (n, m)$ và in nghiệm chuẩn $x$ trong đoạn $0 \leq x < K$ ; toàn bộ nghiệm khi đó là $x + q K$ với $q$ nguyên.

Input

Dòng đầu chứa $T$ . Mỗi dòng trong $T$ dòng tiếp theo chứa bốn số $a$ $n$ $b$ $m$ .

Output

Với mỗi bộ dữ liệu, in no solution nếu vô nghiệm; nếu có nghiệm, in $x$ $K$ , trong đó $K = lcm (n, m)$ và $0 \leq x < K$ .

Constraints

$1 \leq T \leq 1000$ .
$0 \leq a < n, 0 \leq b < m$ .
$1 \leq n, m \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $T \leq 3, n \leq 6$ và $m \leq 8$ .
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung.

Example

Test 1

Input

2
2 4 6 8
1 2 0 4

Output

6 8
no solution

Giải thích: Ở bộ đầu, các số hợp lệ tạo lớp $6$ theo chu kỳ $8$ . Ở bộ thứ hai, một số không thể vừa lẻ theo mô-đun $2$ vừa chia hết cho $4$ , nên hệ vô nghiệm.

Mô hình: Mỗi bộ dữ liệu cho hai điều kiện về số dư của cùng một số nguyên: x mod n = a và x mod m = b. Hai mô-đun có thể có ước chung.
Mô hình: Nếu không có số nguyên nào thỏa đồng thời hai điều kiện, hãy thông báo không có nghiệm. Nếu có, hãy in nghiệm không âm nhỏ nhất x và mô-đun chung K; toàn bộ nghiệm khi đó là x + qK với q nguyên.
Thuật toán: Đặt x=a+n*t. Điều kiện còn lại trở thành:
Thuật toán: n*t ≡ b-a (mod m).
Thuật toán: Gọi g=gcd(n,m). Đồng dư tuyến tính trên có nghiệm khi và chỉ khi g | (b-a). Nếu không chia hết, hệ vô nghiệm.
Thuật toán: Khi chia hết, rút gọn:
Thuật toán: (n/g)*t ≡ (b-a)/g (mod m/g).
Thuật toán: Hai số n/g và m/g nguyên tố cùng nhau, nên lấy nghịch đảo của n/g modulo m/g. Từ đó tìm t nhỏ nhất không âm, tính x=a+nt, rồi chuẩn hóa theo K=lcm(n,m)=n/gm.
Chứng minh đúng đắn: Điều kiện cần: từ nt = (b-a)+mq suy ra g chia b-a. Điều kiện đủ: nếu g chia b-a, phương trình đã rút gọn có hệ số khả nghịch, nên có t. Hai nghiệm bất kỳ có hiệu chia hết cho cả n và m, do đó chia hết cho lcm(n,m); vì vậy lớp nghiệm modulo K là duy nhất.
Độ phức tạp: O(log min(n,m)) mỗi test; O(1) bộ nhớ.
Lỗi thường gặp: Chỉ kiểm tra gcd(n,m)=1 rồi kết luận các trường hợp còn lại vô nghiệm.
Lỗi thường gặp: Dùng K=nm thay vì n/gm.
Lỗi thường gặp: Lấy modulo số âm bằng toán tử % của C++ mà không chuẩn hóa.