P17696 红绿灯

题目来源：【HT-129-Div.1】核桃省选模拟赛 穿行于斑驳的街道。

szh 所在的世界有一条特别的马路。 由于马路是笔直的，所以可以将其视为一条数轴，马路的起点即为数轴的原点，马路上一共有 $n$ 个红绿灯，第 $i$ 个红绿灯和起点的距离为 $s_i$ 个单位长度，即它位于数轴上数值为 $s_i$ 的地方。 这些红绿灯与平常的红绿灯不同，假设你到达第 $i$ 个红绿灯的位置 $s_i$ 的时刻为 $t$，若 $t$ 为 $a$ 的倍数，则你需要停止行驶，等待 $b_i$ 时刻再继续行驶；否则你不用等待，继续行驶。其中 $a$ 为输入给定的值。 现在有 $m$ 个人从起点出发，第 $i$ 个人在时刻 $i$ 出发。每个人在行驶时的速度都视为每时刻行驶 $1$ 个单位长度。 定义 $S_i$ 为所有等了第 $i$ 个红绿灯的人到达第 $i$ 个红绿灯的位置 $s_i$ 的时刻构成的**不可重集**，你需要对于每个 $i$ 求出 $|S_i|$ 的大小。

输入共三行。 第一行输入三个正整数，分别为 $n,a,m$。 第二行输入 $n$ 个正整数，第 $i$ 个整数为 $s_i$。 第三行输入 $n$ 个正整数，第 $i$ 个整数为 $b_i$。

输出共 $n$ 行，第 $i$ 行输出一个整数，表示 $|S_i|$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$1\le m,a,s_i,b_i\le 10^{12}$，$s_{i-1}< s_i$。 | 子任务编号 | $n\le$ | $m\le$ | $a\le$ | 分值 | 特殊性质 | | ----: | ------------: | --------: | --------: | ---: | ------- | | $1$ | $10^3$ | $10^3$ | $10^3$ | $5$ | 无 | | $2$ | $10^3$ | $10^6$ | $10^6$ | $10$ | 无 | | $3$ | $10^3$ | $10^{12}$ | $10^{12}$ | $15$ | 无 | | $4$ | $2\times10^5$ | $10^{12}$ | $10^{12}$ | $20$ | 无 | | $5$ | $10^6$ | $10^6$ | $10^6$ | $15$ | $b_i=a$ | | $6$ | $10^6$ | $10^{12}$ | $10^{12}$ | $15$ | $b_i=a$ | | $7$ | $10^6$ | $10^{12}$ | $10^{12}$ | $20$ | 无 |