G :: Recurs

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Consider the recursive relation fn = afn-1 + bfn-2.

Given f0, f1, n and X, you must find positive integers a and b such that fn = X.

Input

There are multiple test cases in the input. Each test case is a line with four integers f0, f1, n, and (1 <= f0, f1, X <= 109 and 4 <= n <= 109). The input terminates with a line of the form "0 0 0 0" (without quotation marks) which should not be processed as a test case.

Output

For each test case, write a single line containing the two required integers a and b. If there are multiple solutions, write the one with the minimum value of a. If there is no solution, print "No solution" (without quotation marks).

Sample Input

1 2 4 29
1 2 4 7
0 0 0 0

Sample Output

2 1
No solution
Submit

Source: 9th Iran Nationwide Internet Contest