Problem Background

JOI is the owner of the IOI Manor.

Problem Description

IOI Manor currently has $N$ employees, and there are $M$ apple trees around a lake with a circumference of $L$.

The $i$-th employee is $A_i$ meters clockwise from the northernmost point of the lake, and the $i$-th apple tree is $B_i$ meters clockwise from the northernmost point of the lake.

Due to special reasons, each apple tree can have at most one apple. Initially, each tree has one apple, and if an apple is picked, a new one will grow after exactly $C$ seconds.

Each employee starts at their respective position and moves clockwise by 1 meter per second. They will pick an apple if they encounter a tree with a ripe apple.

JOI has given $Q$ queries, where the $i$-th query is:

• How many apples has the $V_i$-th employee harvested by the end of time $T_i$?

Input Format

The first line contains four integers $N, M, L, C$ representing the number of employees, the number of apple trees, the circumference of the lake, and the time it takes for an apple to ripen.
The second line contains $N$ integers $A_i$ as described.
The third line contains $M$ integers $B_i$ as described.
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 a query.

Output Format

Output $Q$ lines, each containing a single integer representing the answer to the corresponding query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
1
1

Sample Input #2

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

Sample Output #2

146
7035
7
7359360
202
10320
0
628
18

Sample Input #3

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

Sample Output #3

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

Notes/Hints

Sample 1 Explanation

• At time $1$:
• Employee $2$ reaches the second apple tree and picks the ripe apple.
• Employee $3$ reaches the first apple tree and picks the ripe apple.
• At time $3$:
• Employee $2$ reaches the first apple tree but finds no ripe apple.

By the end of time $3$, employee $2$ has picked $1$ apple, corresponding to the second query in Sample #1.

• At time $4$:
• Employee $1$ reaches the second apple tree and picks the ripe apple.
• At time $6$:
• Employee $1$ reaches the first apple tree and picks the ripe apple.
• Employee $3$ reaches the second apple tree but finds no ripe apple.

By the end of time $7$, employee $1$ has picked $2$ apples, corresponding to the first query in Sample #1.

• At time $8$:
• Employee $2$ reaches the second apple tree and picks the ripe apple.
• Employee $3$ reaches the first apple tree but finds no ripe apple.

By the end of time $8$, employee $3$ has picked $1$ apple, corresponding to the third query in Sample #1.

Subtasks

For $100\%$ of the data, $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 Harvest.

见题面 Input 部分

见题面 Output 部分