#3278. 「JOISC 2020 Day3」收获

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ShineEternal

题目描述

题目译自 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

样例输出 1

2
1
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

样例输入 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

样例输出 2

146
7035
7
7359360
202
10320
0
628
18

样例输入 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

样例输出 3

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)

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

子任务编号 附加限制 分值
1 N,M,Q\leq 3000 5
2 T_k\geq 10^{15} 20
3 无附加限制 75