← 返回题目列表

Codeforces · 187/D

D. BRT 合同

中文机器翻译题面 查看原题

PMP上一战,他击败了所有对手,晋级决赛。但半决赛结束后,邪恶从背后袭击了他,杀死了他!上帝保佑他。

在他去世之前,PMP 与快速公交系统 (BRT) 签署了一份合同,通过优化出行时间估计来改善公共交通。你应该帮助PMP完成他的最后一份合同。

每条 BRT 线路均为直线,且沿途经过 n 个相交点。每个十字路口都有红绿灯周期性地在绿灯和红灯之间循环。它在零时间开始呈绿色亮起。在持续 g 秒的绿色阶段,允许交通继续进行。绿色阶段之后,灯光变为红色,并保持该颜色 r 秒。在红色阶段,交通禁止继续进行。如果车辆恰好在信号灯变为红色时到达十字路口,则应停车,但如果信号灯刚刚变为绿色,则车辆可以继续行驶。

所有交通信号灯都有相同的时间并且是同步的。换句话说,所有交通灯的红色(和绿色)阶段的周期都是相同的,并且它们都在时间零开始亮起绿色。

BRT公司计算了公交车通过每个路段所需的时间。路段是两个连续交通灯之间或交通灯与源(或目的地)站之间的距离。更准确地说,BRT 专家提供 n + 1 个正整数 li,即公交车从源点到目的地路径中穿过第 i 个路段所需的时间(以秒为单位)。 l1值表示公交车通过源点和第一个交叉路口之间的距离所需的时间。 ln + 1 值表示最后一个路口和目的地之间的时间。

一天后,q 辆公共汽车离开源站。第 i 条总线在时间 ti(以秒为单位)从源开始。 BRT公司的决策者想知道公交车什么时候到达目的地?

巴士被视为点。如果可以的话,公共汽车总是会移动。总线之间互不干扰。

输入

输入的第一行包含三个空格分隔的正整数 n、g、r (1 ≤ n ≤ 105, 2 ≤ g + r ≤ 109) — 交叉点的数量、绿色阶段的持续时间和红色阶段的持续时间。下一行包含 n + 1 个整数 li (1 ≤ li ≤ 109) — 从源到目的地的路径中经过第 i 个路段的时间。

下一行包含一个整数 q (1 ≤ q ≤ 105) — 一天内的公交车数量。接下来 q 行的第 i 行包含一个整数 ti (1 ≤ ti ≤ 109) — 第 i 辆公交车离开源站的时间。

输出

在输出的第 i 行中,您应该打印一个整数 - 第 i 辆公交车到达目的地的时间。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #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

注意

在第一个示例中,公交车#1、#2 和#5 将到达目的地,无需在红灯后等待。但 3 号和 4 号巴士应该等待。

在第二个示例中,第一辆公交车应在第三、第四和第五个十字路口等待。第二辆和第三辆公交车只能在第五个十字路口等待。