Chinese Remainder Theorem
We are given a set of congruence equations. a = a1 (mod n1) a = a2 (mod n2) Where ai are some given constants, which indicates ai = a % ni. The original form of CRT(Chinese Remainder Theorem) states that the given set of congruence equations always has one and exactly one solution modulo m. where m = lcm(n1, n2). Find exactly one value of a. If it's not possible to find the value of a then print "no solution";
1 <= n1, n2 <= 10^9 0 <= a1 < n1 0 <= a2 < n2
The first line of input consists of four integers a1, n1, a2, n2.
Print two integers a, M, where M = lcm(n1, n2) and 0
10000 23000 10000 23000