## RAINBOW2 - Rainbow

This time Blue Mary continues doing meaningless calculations! (see problem SPY) She is interested in calculating the **K**-th power of a very large **N**x**N** 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^{9}.(**D**, **R _{i}** and

**C**may be 0, others must be positive integers.)

_{i}**N**and

**M**will be no more than 10

^{5}.

**R**and

_{i}**C**will be less than

_{i}**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**-th column (0-based) of the matrix

_{i}**A**. As the result may be quite large, output it modulo 10

^{K}^{9}+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 1Output: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 |