AT_joisc2020_h 収穫 (Harvest)

题目描述

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

说明/提示

子任务

对于 $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}$。