一路绿灯

题目描述

小灰灰要沿着一条道路从起点开车到终点，途中依次经过 $n$ 盏交通灯．从起点到第 $1$ 盏灯的行驶时间为 $d_1$，从第 $i-1$ 盏灯到第 $i$ 盏灯的行驶时间为 $d_i$（$2\le i\le n$），从第 $n$ 盏灯到终点的行驶时间为 $d_{n+1}$．

所有交通灯的周期都是 $P$ 秒，但绿灯持续的时间可以不同．对于任意非负整数时刻 $t$，第 $i$ 盏灯的状态为：

• 当 $0\le t\bmod P<g_i$ 时，为绿灯；
• 当 $g_i\le t\bmod P<P$ 时，为红灯．

车辆到达一盏灯时，如果是绿灯，就立即通过；如果是红灯，就停下来，等到这盏灯下一次变为绿灯时立即通过．通过交通灯本身不需要时间．特别地，$g_i=P$ 表示这盏灯始终为绿灯．

小灰灰有 $q$ 个出发方案，第 $j$ 个方案是在时刻 $t_j$ 从起点出发．车辆在各段道路上的行驶时间固定，除了等待红灯之外不会停留．不同方案互不影响，请分别求出每个方案到达终点的时刻．

输入格式

第一行包含三个整数 $n,q,P$，分别表示交通灯数量、出发方案数量和交通灯的周期．

第二行包含 $n+1$ 个整数 $d_1,d_2,\ldots,d_{n+1}$，表示各段道路的行驶时间．

第三行包含 $n$ 个整数 $g_1,g_2,\ldots,g_n$，表示每盏灯在一个周期内的绿灯持续时间．

接下来 $q$ 行，每行包含一个整数 $t_j$，表示第 $j$ 个方案的出发时刻．

输出格式

输出 $q$ 行，每行包含一个整数，依次表示各个方案到达终点的时刻．

样例 1

输入

2 3 5
2 2 1
3 1
0
1
5

输出

6
11
11

解释

• 时刻 $0$ 出发：在时刻 $2$ 到达第 $1$ 盏灯，直接通过；在时刻 $4$ 到达第 $2$ 盏灯，等待到时刻 $5$，最后在时刻 $6$ 到达终点．
• 时刻 $1$ 出发：在时刻 $3$ 到达第 $1$ 盏灯，此时已经是红灯，等待到时刻 $5$；在时刻 $7$ 到达第 $2$ 盏灯，等待到时刻 $10$，最后在时刻 $11$ 到达终点．
• 时刻 $5$ 出发：在时刻 $7$ 到达第 $1$ 盏灯，直接通过；在时刻 $9$ 到达第 $2$ 盏灯，等待到时刻 $10$，最后在时刻 $11$ 到达终点．

下发样例

• Data/sample1.in 与 Data/sample1.ans：题面中的样例．
• Data/sample2.in 与 Data/sample2.ans：$n=q=2000$，满足子任务 $1$．
• Data/sample3.in 与 Data/sample3.ans：$n=2\times 10^5$，$q=20$，满足子任务 $2$．
• Data/sample4.in 与 Data/sample4.ans：$n=q=2\times 10^5$，$P=50$，满足子任务 $3$．
• Data/sample5.in 与 Data/sample5.ans：$n=q=2\times 10^5$，满足子任务 $4$．
• Data/sample6.in 与 Data/sample6.ans：$n=q=2\times 10^5$，该样例无特殊限制．
• Data/sample7.in 与 Data/sample7.ans：$n=q=2\times 10^5$，该样例无特殊限制．

数据规模与约定

对于所有数据，保证：

• $1\le n,q\le 2\times 10^5$；
• $1\le P\le 10^9$；
• $1\le d_i\le 10^9$（$1\le i\le n+1$）；
• $1\le g_i\le P$（$1\le i\le n$）；
• $0\le t_j\le 10^{12}$（$1\le j\le q$）；
• 输入中的所有数均为整数．

本题采用捆绑测试．只有通过某个子任务的全部测试点，才能获得该子任务的分数．

子任务编号	分数	附加限制
$1$	$20$	$n,q\le 2000$
$2$	$15$	$q\le 20$
$3$	$20$	$P\le 50$
$4$	$15$	对所有 $1\le i\le n+1$，$d_i$ 均为 $P$ 的倍数
$5$	$30$	无

大样例下载

点击下载本题选手目录