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\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载