## RAINBOW2 - Rainbow

no tags

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

Ai,j = i * D + Qj

i and j are 0-based index of the row and column of element Ai,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 Ri and Ci.

Input terminates by EOF.

All input numbers are non-negative integers and no more than 109.(D, Ri and Ci may be 0, others must be positive integers.) N and M will be no more than 105. Ri and Ci 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 Ri-th row and Ci-th column (0-based) of the matrix AK. As the result may be quite large, output it modulo 109+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
```

 Added by: Fudan University Problem Setters Date: 2009-05-31 Time limit: 3.332s Source limit: 3332B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: Not My Own Problem