P7217 [JOISC 2020] Harvest

JOI is the owner of the IOI manor.

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.

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 $Q$ lines, each containing one integer, representing the answer.

#### 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 |Subtask|Special Property|Score| |:-:|:-:|:-:| |$1$|$N, M, Q \le 3000$|$5$| |$2$|$T_i \ge 10^{15}$|$20$| |$3$|None|$75$| #### 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](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day3 B 収穫](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day3/harvest.pdf)。 Translated by ChatGPT 5