CF187D.BRT Contract

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.

在PMP的最后一场战争中，他击败了所有对手，成功晋级决赛。但在半决赛结束后，一股邪恶势力从背后袭击了他，并将他杀害！愿上帝保佑他。

临终前，PMP与快速公交系统（BRT）签署了一份合同，该合同旨在通过优化行程时间估计来提升公共交通效率。你需要帮助PMP完成这份最后的合同。

每条BRT线路均为一条直线，沿途经过 $ n $ 个交叉路口。每个交叉路口均设有一盏交通信号灯，其灯光按固定周期在绿色与红色之间循环切换。所有信号灯均于时刻 $ 0 $ 起始亮起绿灯。绿灯持续 $ g $ 秒，在此期间车辆允许通行；绿灯结束后立即转为红灯，并持续 $ r $ 秒，在此期间禁止通行。若一辆车恰好在信号灯变为红灯的瞬间抵达交叉路口，则必须停车；但若信号灯恰于此时变为绿灯，则车辆可直接通行。

所有交通信号灯具有相同的时序且完全同步。换言之，所有信号灯的红灯（及绿灯）相位周期均相同，且全部于时刻 $ 0 $ 同步亮起绿灯。

BRT公司已计算出公交车通过每一段道路所需的时间。所谓“道路段”，指两个相邻交通信号灯之间，或一个交通信号灯与起点站（或终点站）之间的距离。更准确地说，BRT专家提供了 $ n+1 $ 个正整数 $ l_i $，表示公交车沿起点至终点路径行驶第 $ i $ 段道路所需的时间（单位：秒）。其中，$ l_1 $ 表示公交车从起点站行驶至第一个交叉路口所需的时间；$ l_{n+1} $ 表示公交车从最后一个交叉路口行驶至终点站所需的时间。

某日共有 $ q $ 辆公交车从起点站出发。第 $ i $ 辆公交车于时刻 $ t_i $（单位：秒）从起点站出发。BRT公司的决策者希望知道：每辆公交车将于何时抵达终点？

公交车被视为质点。只要允许通行，公交车将始终保持行进状态。各公交车之间互不干扰。

The first line of input contains three space-separated positive integers n, g, r (1 ≤ n ≤ 105, 2 ≤ g + r ≤ 109) — the number of intersections, duration of green phase and duration of red phase. Next line contains n + 1 integers l__i (1 ≤ l__i ≤ 109) — 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 ≤ 105) — the number of buses in a day. The i-th of next q lines contains a single integer t__i (1 ≤ t__i ≤ 109) — the time when i-th bus leaves the source station.

输入的第一行包含三个用空格分隔的正整数 $n$、$g$、$r$（$1 \leq n \leq 10^5$，$2 \leq g + r \leq 10^9$）——分别表示路口数量、绿灯持续时间与红灯持续时间。
第二行包含 $n + 1$ 个整数 $l_i$（$1 \leq l_i \leq 10^9$）——表示从起点到终点路径上第 $i$ 段道路的通行时间。

第三行包含一个整数 $q$（$1 \leq q \leq 10^5$）——表示一天中公交车的数量。
接下来的 $q$ 行中，第 $i$ 行包含一个整数 $t_i$（$1 \leq t_i \leq 10^9$）——表示第 $i$ 辆公交车离开起点站的时间。

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.

在输出的第 $i$ 行中，应打印一个整数——即第 $i$ 辆公交车到达目的地所用的时间。

请注意：在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

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.

在第一个样例中，公交车 #1、#2 和 #5 将无需在红灯后等待即可到达目的地；但公交车 #3 和 #4 需要等待。

在第二个样例中，第一辆公交车应在第三、第四和第五个路口等待；第二和第三辆公交车仅需在第五个路口等待。