题目描述

题目译自 JOISC 2020 Day3 T2「収穫 / Harvest」，感谢 @Chanis 提供翻译。

IOI 庄园有 $N$ 个员工，$M$ 棵苹果树种在湖岸。湖的周长为 $L$ 米。

一开始员工 $i$ 位于从湖的最北端向顺时针方向前进 $A_i$ 米处，所有 $A_i$ 互异。苹果树 $j$ 生长在从湖的最北端向顺时针方向前进 $B_j$ 米处，所有 $B_j$ 互异。

每棵苹果树最多长一个苹果，收获后 $C$ 秒会长出一个新的。时刻 $0$ 时，所有的苹果树上都有一个苹果。员工从时刻 $0$ 开始从各自的地点以 $1\text{m/s}$ 的速度顺时针前进，遇到成熟的苹果就将其摘下（若到达时刚长出苹果，也要摘下），摘苹果的时间忽略不计。

现给出 $Q$ 个询问，第 $k$ 次询问员工 $V_k$ 在时刻 $T_k$ 结束时一共收获到几个苹果。

输入格式

输入第一行为四个整数 $N,M,L,C$，意义由题面所示。

第二行为 $N$ 个整数 $A_1,\ldots,A_N$。

第三行为 $M$ 个整数 $B_1,\ldots,B_M$。

第四行为一个整数 $Q$，即询问的数量。

接下来的 $Q$ 行，每行两个整数 $V_i,T_i$。

输出格式

输出共 $Q$ 行，第 $k$ 行输出一个整数为第 $k$ 个问题的答案。

样例 1

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

2
1
1

• 在第 $1$ 个时刻，员工 $2$ 从第 $2$ 棵苹果树上收获了苹果，员工 $3$ 从第 $1$ 棵苹果树上收获了苹果。

• 在第 $3$ 个时刻，员工 $2$ 到达了第 $1$ 棵苹果树。但是因为那时树上没果子所以没收获。

• 在第 $4$ 个时刻，员工 $1$ 从第 $2$ 棵苹果树上收获了苹果。

• 在第 $6$ 个时刻，员工 $1$ 从第 $1$ 棵苹果树上收获了苹果，员工 $3$ 到达了第 $2$ 棵苹果树，但还是因为那时树上没果子所以没收获。

• 在第 $8$ 个时刻，员工 $2$ 从第 $2$ 棵苹果树上收获了苹果，员工 $3$ 到达了第 $1$ 棵苹果树，但再一次因为那时树上没果子所以没收获。

到第 $7$ 个时刻为止，员工 $1$ 收获了 $2$ 个苹果，故第一行输出 $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

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

数据范围与提示

对于 $100\%$ 的数据，$1 \leq N,M \leq 2\times 10^5$，$N+M \leq L \leq 10^9$，$1 \leq C \leq 10^9$，$1 \leq Q \leq 2\times 10^5$，保证：

• $0 \leq A_{i}<L(1 \leq i \leq N)$；
• $A_{i}<A_{i+1}(1 \leq i \leq N-1)$；
• $0 \leq B_{j}<L(1 \leq j \leq M)$；
• $B_{j}<B_{j+1}(1 \leq j \leq M-1)$；
• $A_{i} \neq B_{j}(1 \leq i \leq N, 1 \leq j \leq M)$；
• $1 \leq V_{k} \leq N(1 \leq k \leq Q)$；
• $1 \leq T_{k} \leq 1000000000000000000=10^{18}(1 \leq k \leq Q)$。

详细子任务及附加限制如下表：