| Codeforces Round 119 (Div. 1) |
|---|
| Закончено |
В последней войне PMP победил всех своих соперников и вышел в финал. Но после окончания полуфинала зло ударило его в спину и убило! Упокой Господь его душу.
Перед смертью PMP подписал контракт с быстрыми автобусными перевозками (БАП), которые улучшают общественный транспорт за счет оптимизации оценки времени путешествия. Вы должны помочь PMP закончить его последний контракт.
Каждая линия БАП — это прямая, проходящая через n перекрестков. На каждом перекрестке есть светофор, который циклически меняется от зеленого к красному. Он начинает светиться зеленым в нулевой момент времени. Во время зеленой фазы, которая длится g секунд, транспорт может проезжать. После зеленой фазы цвет меняется на красный и остается таким r секунд. Во время красной фазы транспорту запрещено проезжать. Если транспортное средство достигает перекрестка ровно в тот момент, когда светофор меняется на красный, оно должно остановиться, но транспортное средство может проезжать, если светофор только что изменил цвет на зеленый.
Все светофоры синхронизированы, то есть во все моменты времени показывают одинаковый свет. Иными словами, период красного (и зеленого) цвета одинаковый для всех светофоров, и все они начинают гореть зеленым в нулевой момент времени.
Компания БАП рассчитала время, необходимое автобусу для того, чтобы проехать каждый участок дороги. Участок дороги — это отрезок дороги между двумя идущими подряд светофорами или станцией отправки (или прибытия). Точнее, специалисты БАП предоставляют n + 1 положительных целых чисел li — время в секундах, необходимое автобусу для проезда по i-му участку дороги на пути от станции отправки до станции прибытия. Число l1 обозначает время, необходимое автобусу для преодоления расстояния между станцией отправки и первым перекрестком. Число ln + 1 обозначает время от последнего перекрестка до станции прибытия.
За день q автобусов покидают станцию отправки. Из них i-ый автобус начинается ехать со станции отправки в момент времени ti (в секундах). Аналитики БАПа хотят знать для каждого автобуса, когда он добирается до станции прибытия.
Автобус считается точкой. Автобус будет всегда двигаться, если это возможно. Автобусы не мешают друг другу.
В первой строке входного файла записаны через пробел три целых положительных числа n, g, r (1 ≤ n ≤ 105, 2 ≤ g + r ≤ 109) — количество перекрестков, продолжительность зеленой фазы и продолжительность красной фазы. В следующей строке записано n + 1 целых чисел li (1 ≤ li ≤ 109) — время, за которое преодолевается i-ый участок дороги на пути из станции отправления к станции прибытия.
Следующая строка содержит единственное целое число q (1 ≤ q ≤ 105) — количество автобусов за день. На i-ой из следующих q строк записано целое число ti (1 ≤ ti ≤ 109) — время выезда i-го автобуса со станции отправления.
На i-ой строке выходного файла выведите единственное целое число — время, когда i-ый автобус достигает станции прибытия.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
1 3 2
5 2
5
1
2
3
4
5
8
9
12
12
12
5 3 7
10 1 1 8 900000005 1000000000
3
1
10
1000000000
1900000040
1900000040
2900000030
В первом тестовом примере, автобусы #1, #2 и #5 достигнут станции прибытия, не останавливаясь на красный свет. Автобусам #3 и #4 придется подождать пока загорится зеленый.
Во втором примере, первый автобус должен подождать на третьем, четвертом и пятом перекрестке. Второй и третий автобусы будут ждать зеленого только на пятом перекрестке.
