D. BRT Contract

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Автобусны шугам нь $n$ огтлолцол бүхий шулуун замаас бүрддэг ба уулзвар бүр дээр ногоон болон улаан гэрлүүд ээлжлэн асах гэрлэн дохионууд байрладаг. Бүх гэрлэн дохионууд 0-р агшинд ногоон гэрэлтэйгээр эхлэцгээдэг. Ногоон гэрэл нь $g$ секунд үргэлжилдэг бөгөөд ногоон гэрэл ассан үед байгаа үед тухайн уулзвараар автобус саадгүй явна. Харин улаан гэрэл ассан($r$ ceкунд үргэлжлэнэ) үед автобус тухайн уулзвар дээрээ зогсон гэрэл ногоон болохыг хүлээх ёстой.Жишээ нь автобус уулзвар яг улаан гэрэл асах мөчид ирлээ гэхэд ногоон гэрэл асах хүртэл ёстой ба харин яг ногоон гэрэл асах мөчид ирлээ гэхэд цааш үргэлжлүүлэн явж болно.

Бүх гэрлэн дохионууд хоорондоо холбоотой тул нэгэн зэрэг өнгөө солицгоодог. Өөрөөр хэлвэл улаан болон ногоон гэрлийн үеүүд нь гэрлэн дохио бүрийн хувьд ижил бөгөөд бүгд эхний 0-р мөчид ногоон гэрэлтэйгээр эхлэцгээдэг.

Автобусны компани замын сегмент бүрийг автобус хэдий хэр хугацаанд туулахыг тооцсон. Сегмент гэдэг нь залгаа хоёр уулзвар хоорондын эсвэл уулзвар эхлэл/төгсгөл хоорондын зай юм. Илүү нарийн тодорхойлвол бидэнд $n+1$ ширхэг бүхэл тоонууд байгаа ба тэдгээрийн $l_i$ нь $i$-р сегментийг автобус хэдий хугацаанд туулахыг секундээр илэрхийлнэ. $l_1$ нь эхний буудлаас эхний уулзвар хүртэл хэдэн секунд явдагийг илэрхийлж байгаа бол $l_{n+1}$ нь сүүлийн уулзвараас сүүлийн зогсоол хүртэл хэдэн секунд явдагийг илэрхийлнэ.

Нэг өдөрт $q$ ширхэг автобус эхний буудлаас хөдөлдөг. $i$-р автобус нь $t_i$-р секундэд эхний буудлаас гардаг бол автобус тус хэддэх хэддэх секундүүдэд эцсийн буудалдаа очихыг олно уу6

Автобуснуудыг цэг гэж үзэж болох ба автобуснууд хөдлөхдөө бие биендээ садаа болдоггүй, улаан гэрэлтэй тулаагүй л бол ямагт хөдлөж байх болно.

Оролт

Эхний мөрөнд уулзваруудын тоо, ногоон гэрлийн болон улаан гэрлийн үргэлжлэх хугацаануудыг $n, g, r(1<=n<=10^5, 2<=g+r<=10^9)$ тоонууд байрлах ба дараагийн мөрөнд $n+1$ ширхэг бүхэл тоонууд $l_i(1<=l_i<=10^9)$ байрлана. $l_i$ нь $i$-р хэсгийг туулахад зарцуулах хугацаа.

Дараагийн мөрөнд автобуснуудын тоо $q(1<=q<=10^5)$ байрлана. Дараагийн $q$ мөрнүүдийн $i$-р мөр нь эерэг бүхэл тоо $t_i(1<=t_i<=10^9)$-г агуулах ба энэ нь $i$-р автобусны эхний буудлаас гарах цагийг секундээр илэрхийлнэ.

Гаралт

Гаралтын $i$-р мөрөнд $i$-р автобус хэддэх секундэд сүүлийн буудал очихыг хэвлэ.

Орчуулсан: devman

Жишээ тэстүүд

Оролт
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 хүлээх хэрэгтэй.

Хоёр дугаар жишээнд хамгийн эхний автобус 3, 4, 5 дахь уулзвар дээр хүлээх хэрэгтэй. 2, 3-р автобусууд зөвхөн 5 дахь уулзвар дээр л хүлээнэ.

Сэтгэгдлүүдийг ачааллаж байна...