Many problems have solutions involving linear recurrence equations of the form f(n) = a · f(n-1) + b · f(n-2) (n ≥ 2). Usually the coefficients a and b are between 0 and 10, so it would be useful to have a program which checks if some given values can be produced by such a recurrence equation. Since the growth of the values f(n) can be exponential, we will consider the values modulo some integer constant k.

More specifically you will be given f(0), f(1), k and some value pairs (i , x_i), where x_i is the remainder of the division of f(i) by k.

You have to determine coefficients a and b for the recurrence equation f such that for each given value pair (i, x_i) the equation x_i = f(i) mod k holds.

Hints

You can write the recurrence equation as follows:

Let

Then, . These equations also apply if everything is calculated modulo k. To speed up the calculation of Aⁿ, the identity Aⁿ = (A^{n div 2})² · A^{n mod 2} may be used. Also, (a · b) mod c = ((a mod c) · (b mod c)) mod c.

Input

The first line of the input contains a number T ≤ 20 which indicates the number of test cases to follow.

Each test case consists of 3 lines. The first line of each test case contains the three integers f(0), f(1) and k, where 2 ≤ k ≤ 10000 and 0 ≤ f(0),f(1) < k. The second line of each test case contains a number m ≤ 10 indicating the number of value pairs in the next line. The third line of each test case contains m value pairs (i,x_i), where 2 ≤ i ≤ 1000000000 and 0 ≤ x_i < k.

Output

For each test case print one line containing the values a and b separated by a space character, where 0 ≤ a,b ≤ 10. You may assume that there is always a unique solution.

Example

Input:
2
1 1 1000
3
2 2 3 3 16 597
0 1 10000
4
11 1024 3 4 1000000000 4688 5 16

Output:
1 1
2 0