P7217 [JOISC 2020] 収穫

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$ 行每行一个整数代表答案。

#### 样例 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