【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$行，一行一个整数表示答案。
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上的苹果，因为苹果没有长出来。
因此员工1在前7秒收获了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
数据范围
子任务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}$