This time Blue Mary continues doing meaningless calculations! (see problem SPY) She is interested in calculating the K-th power of a very large NxN matrix A, where

A_i,j = i * D + Q^j

i and j are 0-based index of the row and column of element A_i,j, respectively.

Now she needs your help (again).

To keep the output small, you are only asked to output some of its elements.

Input

Multiple test cases.

The first line of each test case contains 5 space-separated integers N, K, D, Q, M in this order. M lines follow, each contains two space-separated integers R_i and C_i.

Input terminates by EOF.

All input numbers are non-negative integers and no more than 10⁹.(D, R_i and C_i may be 0, others must be positive integers.) N and M will be no more than 10⁵. R_i and C_i will be less than N.

Input is almost uniformly-random generated, and the number of "large" test cases is relatively small.

Output

For each test case output exactly M lines. Each line contains only one integer: The number at the R_i-th row and C_i-th column (0-based) of the matrix A^K. As the result may be quite large, output it modulo 10⁹+2015.

Example

Input:
10 3 0 1 10
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
2 2 1 2 4
0 0
0 1
1 0
1 1

Output:
100
100
100
100
100
100
100
100
100
100
5
8
8
13