BRT Contract

题意翻译

泰迪每天都要通过一条路从家到学校，这条路的起点是泰迪家，终点则是学校。 这条路中间还有 $n$ 个路口，从第 $i - 1$ 个路口走到第 $i$ 个路口需要 $d_i$ 秒，每个路口都有一个红绿灯。更具体地，绿灯持续时间是 $g$ 秒，红灯持续时间是 $r$ 秒。每天从第 $0$ 秒开始，所有灯都是绿灯，持续 $g$ 秒之后变为红灯，再过 $r$ 秒变成绿灯，以此类推，并且同一时刻所有灯都是相同状态。当泰迪到达一个路口，若是绿灯则可直接通过，若是红灯则需原地等待至绿灯。若到达某一路口时灯的状态正好发生改变，则视到达路口时灯的颜色为其改变后的颜色，例如第 $g$ 秒到达一个路口则视为遇到红灯。 现在泰迪预计了接下来 $q$ 天从家出发的时间，第 $j$ 天将会在第 $t_j$ 秒从家出发，他希望你告诉他每天到达学校的最早时间。你可以假定一天内泰迪一定可以到达学校。 保证 $n, q \leq 10^5, 2 \leq g, r \leq 10^9, d_i, t_j \leq 10^9$。

题目描述

In the last war of PMP, he defeated all his opponents and advanced to the final round. But after the end of semi-final round evil attacked him from behind and killed him! God bless him. Before his death, PMP signed a contract with the bus rapid transit (BRT) that improves public transportations by optimizing time of travel estimation. You should help PMP finish his last contract. Each BRT line is straight line that passes $ n $ intersecting on its ways. At each intersection there is traffic light that periodically cycles between green and red. It starts illuminating green at time zero. During the green phase which lasts for $ g $ seconds, traffic is allowed to proceed. After the green phase the light changes to red and remains in this color for $ r $ seconds. During the red phase traffic is prohibited from proceeding. If a vehicle reaches the intersection exactly at a time when the light changes to red, it should stop, but the vehicle is clear to proceed if the light has just changed to green. All traffic lights have the same timing and are synchronized. In other words the period of red (and green) phase is the same for all of traffic lights and they all start illuminating green at time zero. The BRT Company has calculated the time that a bus requires to pass each road segment. A road segment is the distance between two consecutive traffic lights or between a traffic light and source (or destination) station. More precisely BRT specialists provide $ n+1 $ positive integers $ l_{i} $ , the time in seconds that a bus needs to traverse $ i $ -th road segment in the path from source to destination. The $ l_{1} $ value denotes the time that a bus needs to pass the distance between source and the first intersection. The $ l_{n+1} $ value denotes the time between the last intersection and destination. In one day $ q $ buses leave the source station. The $ i $ -th bus starts from source at time $ t_{i} $ (in seconds). Decision makers of BRT Company want to know what time a bus gets to destination? The bus is considered as point. A bus will always move if it can. The buses do not interfere with each other.

输入输出格式

输入格式

The first line of input contains three space-separated positive integers $ n,g,r $ ( $ 1<=n<=10^{5},2<=g+r<=10^{9} $ ) — the number of intersections, duration of green phase and duration of red phase. Next line contains $ n+1 $ integers $ l_{i} $ ( $ 1<=l_{i}<=10^{9} $ ) — the time to pass the $ i $ -th road segment in the path from source to destination. Next line contains a single integer $ q $ ( $ 1<=q<=10^{5} $ ) — the number of buses in a day. The $ i $ -th of next $ q $ lines contains a single integer $ t_{i} $ ( $ 1<=t_{i}<=10^{9} $ ) — the time when $ i $ -th bus leaves the source station.

输出格式

In the $ i $ -th line of output you should print a single integer — the time that $ i $ -th bus gets to destination. Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

1 3 2
5 2
5
1
2
3
4
5

输出样例 #1

8
9
12
12
12

输入样例 #2

5 3 7
10 1 1 8 900000005 1000000000
3
1
10
1000000000

输出样例 #2

1900000040
1900000040
2900000030

说明

In the first sample, buses #1, #2 and #5 will reach the destination without waiting behind the red light. But buses #3 and #4 should wait. In the second sample, first bus should wait at third, fourth and fifth intersections. Second and third buses should wait only at the fifth intersection.

题意翻译

泰迪每天都要通过一条路从家到学校，这条路的起点是泰迪家，终点则是学校。 这条路中间还有 $n$ 个路口，从第 $i - 1$ 个路口走到第 $i$ 个路口需要 $d_i$ 秒，每个路口都有一个红绿灯。更具体地，绿灯持续时间是 $g$ 秒，红灯持续时间是 $r$ 秒。每天从第 $0$ 秒开始，所有灯都是绿灯，持续 $g$ 秒之后变为红灯，再过 $r$ 秒变成绿灯，以此类推，并且同一时刻所有灯都是相同状态。当泰迪到达一个路口，若是绿灯则可直接通过，若是红灯则需原地等待至绿灯。若到达某一路口时灯的状态正好发生改变，则视到达路口时灯的颜色为其改变后的颜色，例如第 $g$ 秒到达一个路口则视为遇到红灯。 现在泰迪预计了接下来 $q$ 天从家出发的时间，第 $j$ 天将会在第 $t_j$ 秒从家出发，他希望你告诉他每天到达学校的最早时间。你可以假定一天内泰迪一定可以到达学校。 保证 $n, q \leq 10^5, 2 \leq g, r \leq 10^9, d_i, t_j \leq 10^9$。