G :: Recurs

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Consider the recursive relation f_n = af_n-1 + bf_n-2.

Given f₀, f₁, n and X, you must find positive integers a and b such that f_n = X.

Input

There are multiple test cases in the input. Each test case is a line with four integers f₀, f₁, n, and (1 <= f₀, f₁, X <= 10⁹ and 4 <= n <= 10⁹). 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