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";
Input Format
The first line of input consists of four integers a1, n1, a2, n2.
Output Format
Print two integers a, M, where M = lcm(n1, n2) and 0 <= a < M, giving the solution a (mod M) to the equations a = a1 (mod n1) a = a2 (mod n2) Print "no solution" if there is no solution for a given set of congruence equations;
Constraints
1 <= n1, n2 <= 10^9 0 <= a1 < n1 0 <= a2 < n2
Example
Input
10000 23000 10000 23000
Output
10000 23000