Background

JOI is the owner of the IOI manor.

Problem Description

There are $N$ employees in the IOI manor, and there are $M$ apple trees along the shore of a lake with perimeter $L$.

Employee $i$ is located $A_i$ meters clockwise from the northernmost point of the lake. Apple tree $i$ is located $B_i$ meters clockwise from the northernmost point of the lake.

For special reasons, each apple tree can have at most one apple. At the initial moment, each apple tree has $1$ apple. If the apple on a tree is picked, then exactly $C$ s later an apple will grow again.

At the initial moment, each employee is at their original position. At each time moment, they walk $1$ meter clockwise. When they encounter an apple tree with a ripe apple, they will pick the apple.

Now JOI gives $Q$ queries. Query $i$ is:

• Ask how many apples employee $V_i$ has harvested after time $T_i$ ends.

Input Format

The first line contains four integers $N, M, L, C$, representing the number of employees, the number of apple trees, the perimeter of the lake, and the time interval for apples to become ripe again.
The second line contains $N$ integers $A_i$ as described above.
The third line contains $M$ integers $B_i$ as described above.
The fourth line contains an integer $Q$, representing the number of queries.
The next $Q$ lines each contain two integers $V_i, T_i$, representing one query.

Output Format

Output $Q$ lines, each containing one integer, representing the answer.

3 2 7 3
1 4 6
0 5
3
1 7
2 3
3 8

2
1
1

5 3 20 6
0 4 8 12 16
2 11 14
9
4 1932
2 93787
1 89
5 98124798
1 2684
1 137598
3 2
3 8375
4 237

146
7035
7
7359360
202
10320
0
628
18

8 15 217 33608
0 12 71 96 111 128 152 206
4 34 42 67 76 81 85 104 110 117 122 148 166 170 212
14
2 223544052420046341
3 86357593875941375
4 892813012303440034
1 517156961659770735
7 415536186438473633
6 322175014520330760
7 557706040951533058
6 640041274241532527
5 286263974600593111
8 349405886653104871
1 987277313830536091
5 989137777159975413
2 50689028127994215
7 445686748471896881

33230868503053
3
5
1
123542793648997
8
165811220737767
8
7
1
1
7
7535161012043
132506837660717

Hint

Explanation of Sample 1

• At time $1$:
  • Employee $2$ arrives at apple tree $2$ and picks the ripe apple.
  • Employee $3$ arrives at apple tree $1$ and picks the ripe apple.
• At time $3$:
  • Employee $2$ arrives at apple tree $1$, but there is no ripe apple.

After time $3$ ends, employee $2$ has picked $1$ apple in total, corresponding to the 2nd query of Sample 1.

• At time $4$:
  • Employee $1$ arrives at apple tree $2$ and picks the ripe apple.
• At time $6$:
  • Employee $1$ arrives at apple tree $1$ and picks the ripe apple.
  • Employee $3$ arrives at apple tree $2$, but there is no ripe apple.

After time $7$ ends, employee $1$ has picked $2$ apples in total, corresponding to the 1st query of Sample 1.

• At time $8$:
  • Employee $2$ arrives at apple tree $2$ and picks the ripe apple.
  • Employee $3$ arrives at apple tree $1$, but there is no ripe apple.

After time $8$ ends, employee $3$ has picked $1$ apple in total, corresponding to the 3rd query of Sample 1.

Subtasks

Constraints

For $100\%$ of the testdata: $1 \le N, M, Q \le 2 \times 10^5$, $N + M \le L$, $1 \le C, L \le 10^9$, $0 \le A_i, B_i < L$, $A_i < A_{i+1}$, $B_i < B_{i+1}$, $A_i \ne B_i$, $1 \le V_i \le N$, $1 \le T_i \le 10^{18}$.

Notes

Translated from The 19th Japanese Olympiad in Informatics Spring Training Camp Day3 B 収穫。

Translated by ChatGPT 5