IOI Manor Apple Harvest

There are N employees at IOI Manor and M apple trees planted along the shore of a circular lake with circumference L.

The i^th employee starts from the northmost point of the lake and has walked A_i meters in the clockwise direction. Similarly, the i^th apple tree is located B_i meters clockwise from the northmost point.

Initially, every apple tree bears exactly one apple. However, once an apple is picked from a tree, that tree will regrow an apple exactly C seconds later (each tree can have at most one apple at any time).

At time 0, every employee stands at his/her starting position. Every second, each employee moves clockwise by 1 meter. If an employee encounters an apple tree that currently has a ripe apple, the employee will immediately pick it.

You are given Q queries. The i^th query asks: How many apples does employee V_i collect by the end of time T_i (i.e. after T_i seconds)?

Note: When an employee reaches a tree at exactly the same time the apple regrows, the apple can be picked immediately.

Hint: For an employee starting at position A and an apple tree at position B, let d = (B - A + L) mod L denote the distance the employee must travel (clockwise) to reach that tree for the first time. The employee will then revisit that tree every L seconds thereafter. Using this observation, you may simulate or mathematically determine the number of apples picked from each tree.

inputFormat

The input consists of multiple lines:

1. The first line contains five integers N, M, L, C, and Q separated by spaces.
2. The second line contains N integers: A₁, A₂, ..., A_N, where A_i is the initial distance (in meters) the i^th employee has walked from the northmost point.
3. The third line contains M integers: B₁, B₂, ..., B_M, where B_i represents the position of the i^th apple tree (in meters clockwise from the northmost point).
4. Each of the next Q lines contains two integers: V_i and T_i, representing a query asking for the number of apples collected by the V_i^th employee by time T_i.

outputFormat

For each query, output a single integer in a new line denoting the number of apples collected by the specified employee by time T.

sample

1 1 10 5 3
0
0
1 0
1 5
1 10

1
1
2