#P17734. 收获

收获

题目描述

现在奶龙庄园有 NN 名员工,在周长为 LL 的湖的湖岸边有 MM 棵苹果树。

第 ii 名员工从湖的最北点顺时针走了 AiA_i 米,第 ii 棵苹果树长在从湖的最北点顺时针的 BiB_i 米。

因为特殊原因,每棵苹果树上最多长一个苹果,初始时刻每棵苹果树上都有 11 个苹果,如果一棵树上的苹果被摘掉了,在恰好 CC s 后会长出一个苹果。

每名员工在初始时刻都在自己原本的位置,每过一个时刻就会顺时针走 11 米,遇到有成熟苹果的苹果树就会把苹果摘下来。

现在奶龙给定了 QQ 个询问,第 ii 个询问为:

询问第 ViV_i 个员工在时刻 TiT_i 结束后收获到几个苹果。

输入格式

从文件 harvest.in 中读入数据。

第一行四个整数 N,M,L,CN,M,L,C 代表员工数、苹果树数、湖的周长、苹果每隔一定时间成熟。

第二行 NN 个整数 AiA_i,如题目所示。

第三行 MM 个整数 BiB_i,如题目所示。

第四行一个整数 QQ 代表询问次数。

接下来 QQ 行每行两个整数 Vi,TiV_i,T_i 代表一个询问。

输出格式

输出到文件 harvest.out 中。

QQ 行,每行一个整数代表答案。

样例输入 1

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

样例输出 1

2
1
1

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

样例解释 1

在时刻 11:员工 22 到达第 22 棵苹果树,并采摘了成熟的苹果;员工 33 到达第 11 棵苹果树,并采摘了成熟的苹果。

在时刻 33:员工 22 到达第 11 棵苹果树,但没有成熟的苹果。

到时刻 33 结束后,员工 22 共采摘了 11 个苹果,对应样例 11 的第 22 个询问。

在时刻 44:员工 11 到达第 22 棵苹果树,并采摘了成熟的苹果。

在时刻 66:员工 11 到达第 11 棵苹果树,并采摘了成熟的苹果;员工 33 到达第 22 棵苹果树,但没有成熟的苹果。

到时刻 77 结束后,员工 11 共采摘了 22 个苹果,对应样例 11 的第 11 个询问。

在时刻 88:员工 22 到达第 22 棵苹果树,并采摘了成熟的苹果;员工 33 到达第 11 棵苹果树,但没有成熟的苹果。

到时刻 88 结束后,员工 33 共采摘了 11 个苹果,对应样例 11 的第 33 个询问。

测试点约束

对于 100%100\% 的数据:

  • 1≤N,M,Q≤2×1051\le N,M,Q\le 2\times 10^5;
  • N+M≤LN+M\le L;
  • 1≤C,L≤1091\le C,L\le 10^9;
  • 0≤Ai,Bi<L0\le A_i,B_i<L;
  • Ai<Ai+1A_i<A_{i+1},Bi<Bi+1B_i<B_{i+1},Ai≠BiA_i\ne B_i;
  • 1≤Vi≤N1\le V_i\le N,1≤Ti≤10181\le T_i\le 10^{18}。
子任务编号 特殊性质 分值
1 N,M,Q≤3000N,M,Q\le 3000 15
2 Ti≥1015T_i\ge 10^{15} 35
3 无 50