题目背景

JOI 君是 IOI 庄园的庄园主。

题目描述

现在 IOI 庄园有 $N$ 名员工，在周长为 $L$ 的湖的湖岸边有 $M$ 棵苹果树。

第 $i$ 名员工从湖的最北点顺时针走了 $A_i$ 米，第 $i$ 棵苹果树长在从湖的最北点顺时针的 $B_i$ 米。

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

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

现在 JOI 君给定了 $Q$ 个询问，第 $i$ 个询问为：

• 询问第 $V_i$ 个员工在时刻 $T_i$ 结束后收获到几个苹果。

输入格式

第一行四个整数 $N,M,L,C$ 代表员工数，苹果树数，湖的周长，苹果每隔一定时间成熟。
第二行 $N$ 个整数 $A_i$ 如题目所示。
第三行 $M$ 个整数 $B_i$ 去题目所示。
第四行一个整数 $Q$ 代表询问次数。
接下来 $Q$ 行每行两个整数 $V_i,T_i$ 代表一个询问。

输出格式

$Q$ 行每行一个整数代表答案。

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

2
1
1

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 解释

• 在时刻 $1$：
  • 员工 $2$ 到达第 $2$ 棵苹果树，并采摘了成熟的苹果
  • 员工 $3$ 到达第 $1$ 棵苹果树，并采摘了成熟的苹果
• 在时刻 $3$：
  • 员工 $2$ 到达第 $1$ 棵苹果树，但没有成熟的苹果

到时刻 $3$ 结束后，员工 $2$ 共采摘了 $1$ 个苹果，对应样例 $1$ 的第 $2$ 个询问。

• 在时刻 $4$：
  • 员工 $1$ 到达第 $2$ 棵苹果树，并采摘了成熟的苹果
• 在时刻 $6$：
  • 员工 $1$ 到达第 $1$ 棵苹果树，并采摘了成熟的苹果
  • 员工 $3$ 到达第 $2$ 棵苹果树，但没有成熟的苹果

到时刻 $7$ 结束后，员工 $1$ 共采摘了 $2$ 个苹果，对应样例 $1$ 的第 $1$ 个询问。

• 在时刻 $8$：
  • 员工 $2$ 到达第 $2$ 棵苹果树，并采摘了成熟的苹果
  • 员工 $3$ 到达第 $1$ 棵苹果树，但没有成熟的苹果

到时刻 $8$ 结束后，员工 $3$ 共采摘了 $1$ 个苹果，对应样例 $1$ 的第 $3$ 个询问。

子任务

子任务	特殊性质	分数
$1$	$N,M,Q \le 3000$	$5$
$2$	$T_i \ge 10^{15}$	$20$
$3$	无	$75$

对于 $100\%$ 的数据，$1 \le N,M,Q \le 2 \times 10^5$，$N+M \le L$，$1 \le C,L \le 10^9$，$0 \le A_i,B_i < L$，$A_i<A_{i+1}$，$B_i<B_{i+1}$，$A_i \ne B_i$，$1 \le V_i \le N$，$1 \le T_i \le 10^{18}$。

说明

翻译自 第１９回日本情報オリンピック　春季トレーニング合宿 Day3 B 収穫。