UOJ Logo Universal Online Judge

UOJ

#508. 【JOISC2020】收获

统计

IOI 农场是一个种植苹果的农场。他以位于一个巨大的环形湖周边而闻名。在IOI农场里共有$N$个员工,编号依次为$1$至$N$。共有$M$棵苹果树,编号依次为$1$至$M$。湖的周长为 $L$ 米。在时刻0,第$i$位员工站在离湖最北边的地方顺时针走$A_i$米的位置。第$i$棵苹果树在离湖最北边的地方顺时针走$B_i$米的位置。保证$A_i,B_i$互不相同。

由于IOI农场苹果树是经过改良的特殊品种,一棵树同时只能结一个苹果。同时,如果一颗树上的苹果被摘掉了,在恰好$C$秒钟后会长出一个苹果。初始每颗树上都有一个苹果,同时每个员工开始沿着顺时针方向移动。每个员工的移动速度是1米每秒。如果一个员工在某一时刻到达了一颗长有苹果的苹果树,他会摘掉这个苹果(如果在到达时恰好长出苹果,员工也会摘掉)。这里我们忽略员工摘苹果的时间。

K主席是IOI农场的股东。因为你是IOI农场的一名管理人员,K主席会不断问你每个员工的工作效率。更一般的,K主席会有$Q$个问题。第$i$个问题是询问第$V_k$个员工在前$T_k$前收获的苹果数量。第$T_k$秒收获的苹果计入答案。

你需要编写程序回答K主席的询问。

输入格式

第一行四个正整数$N,M,L,C$。

第二行$N$个非负整数,第$i$个数表示$A_i$。

第三行$M$个非负整数,第$i$个数表示$B_i$。

第四行一个正整数$Q$。

接下来$Q$行,一行两个正整数$V_k,T_k$,表示一次询问。

输出格式

$Q$行,一行一个整数表示答案。

样例一

input

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

output

2
1
1

explanation

  • 在第1秒,员工2收获一个苹果树2上的苹果,员工3收获一个苹果树1上的苹果。
  • 在第3秒,员工2没有收获苹果树1上的苹果,因为苹果没有长出来。
  • 在第4秒,员工1收获一个苹果树2上的苹果。
  • 在第6秒,员工1收获一个苹果树1上的苹果,员工3没有收获苹果树2上的苹果,因为苹果没有长出来。
  • 在第8秒,员工2收获一个苹果树2上的苹果,员工3没有收获苹果树1上的苹果,因为苹果没有长出来。

因此员工1在前7秒收获了2个苹果,于是在第一行输出2。

样例二

input

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

output

146
7035
7
7359360
202
10320
0
628
18

样例三

input

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

output

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

数据范围

子任务1($5$分): $N,M,Q \le 3000$。

子任务2($20$分): $T_i \ge 10^{15}$。

子任务3($75$分): 无特殊限制。

对于所有测试数据,满足$1 \le N,M,Q \le 200000,N+M \le L \le 10^9,1 \le C \le 10^9$。

对于所有测试数据,满足$0 \le A_i,B_i < L,A_i < A_{i+1}(1 \le i < N),B_i < B_{i+1}(1 \le i < N)$。

对于所有测试数据,满足$1 \le V_k \le N,1 \le T_k \le 10^{18}$。

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载