IOI 农场是一个种植苹果的农场，因其坐落在一个巨大的圆形湖泊周围而闻名。

在 IOI 农场中，有 $N$ 名员工，编号为 $1$ 到 $N$。有 $M$ 棵苹果树，编号为 $1$ 到 $M$。湖泊的周长为 $L$ 米。

起初，员工 $i$ ($1 \le i \le N$) 在距离湖泊最北端顺时针 $A_i$ 米处等待。$A_i$ ($1 \le i \le N$) 的值各不相同。苹果树 $j$ ($1 \le j \le M$) 生长在距离湖泊最北端顺时针 $B_j$ 米处。$B_j$ ($1 \le j \le M$) 的值各不相同。此外，没有任何员工的初始位置有苹果树。

由于 IOI 农场对苹果树进行了特殊品种改良，每棵苹果树在同一时间最多只能有一个苹果。此外，如果从苹果树上采摘了一个苹果，它将在恰好 $C$ 秒后长出一个新苹果。在时间 $0$ 时，每棵苹果树上都有一个苹果，并且每位员工开始沿顺时针方向绕湖行走。每位员工的速度为每秒 $1$ 米。如果一名员工到达一棵有苹果的苹果树，该员工总是会采摘它（如果一名员工到达时苹果树恰好长出了一个新苹果，该员工也会采摘它）。我们忽略员工采摘苹果所需的时间。

K 总裁是 IOI 农场的股东。作为 IOI 农场的经理，K 总裁要求你报告员工的效率。更准确地说，K 总裁想知道以下 $Q$ 个值。

对于每个 $k$ ($1 \le k \le Q$)，计算员工 $V_k$ 在时间 $T_k$ 之前（包括在时间 $T_k$ 恰好采摘的苹果）采摘的苹果总数。

编写一个程序，给定员工数量、苹果树数量、湖泊周长、苹果树长出新苹果所需的时间、员工和苹果树的位置，以及 $Q$ 个查询的信息，计算每个查询中采摘的苹果数量。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N \ M \ L \ C$ $A_1 \ \dots \ A_N$ $B_1 \ \dots \ B_M$ $Q$ $V_1 \ T_1$ $\vdots$ $V_Q \ T_Q$

输出格式

向标准输出写入 $Q$ 行。在第 $k$ 行 ($1 \le k \le Q$)，输出第 $k$ 个查询的答案。

数据范围

• $1 \le N \le 200\,000$
• $1 \le M \le 200\,000$
• $N + M \le L \le 1\,000\,000\,000$
• $1 \le C \le 1\,000\,000\,000$
• $0 \le A_i < L$ ($1 \le i \le N$)
• $A_i < A_{i+1}$ ($1 \le i \le N - 1$)
• $0 \le B_j < L$ ($1 \le j \le M$)
• $B_j < B_{j+1}$ ($1 \le j \le M - 1$)
• $A_i \neq B_j$ ($1 \le i \le N, 1 \le j \le M$)
• $1 \le Q \le 200\,000$
• $1 \le V_k \le N$ ($1 \le k \le Q$)
• $1 \le T_k \le 1\,000\,000\,000\,000\,000\,000 = 10^{18}$ ($1 \le k \le Q$)

子任务

1. (5 分) $N \le 3\,000, M \le 3\,000, Q \le 3\,000$
2. (20 分) $T_k \ge 1\,000\,000\,000\,000\,000 = 10^{15}$ ($1 \le k \le Q$)
3. (75 分) 无附加限制

样例

输入格式 1

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

输出格式 1

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$ 之前（包括在时间 $7$ 采摘的苹果）采摘的苹果总数为 $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