409458: GYM103566 F Прыгай вперед!

F. Прыгай вперед!ограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Федот решил пройти уровень в своей любимой игре «Прыгай вперед!». Уровень представляет из себя $$$n$$$ последовательных клеток, которые пронумерованы числами от $$$1$$$ до $$$n$$$. За посещение клетки с номером $$$i$$$ необходимо заплатить $$$a_i$$$ тугриков. У каждой клетки есть выталкивающая сила, которая изначально равна одному (это означает, что из клетки с номером $$$i$$$ можно прыгнуть только в клетку с номером $$$i + 1$$$). Цель состоит в том, чтобы пройти из клетки номер $$$1$$$ в клетку номер $$$n$$$, потратив как можно меньше тугриков.

Понятно, что в таких условиях уровень можно пройти единственным образом — последовательно посетить все клетки от первой до последней. А стоимость такого прохождения будет равна сумме стоимостей посещения всех клеток уровня. Но все не так просто, ведь в игре есть $$$n - 1$$$ дополнительных карточек, пронумерованных числами от $$$1$$$ до $$$n - 1$$$. На карточке номер $$$i$$$ записано число $$$b_i$$$ ($$$1 \le b_i \le n - i$$$), которое означает, что если применить $$$i$$$-ю карточку, то выталкивающая сила клетки с номером $$$i$$$ станет равна $$$b_i$$$ и после этого из клетки с номером $$$i$$$ можно будет прыгнуть только в клетку с номером $$$i + b_i$$$. Примененная один раз карточка действует $$$\textbf{на все последующие прохождения}$$$ уровня.

Федот решил применить $$$q$$$ ($$$1 \le q \le n - 1$$$) карточек. Он будет применять их в определенном порядке и после каждого такого действия заново вычислять минимальное количество тугриков, которое нужно потратить, чтобы пройти из клетки номер $$$1$$$ в клетку номер $$$n$$$. Можно доказать, что как бы мы не применяли карточки, всегда найдется путь из клетки номер $$$1$$$ в клетку номер $$$n$$$.

И тут Федот понял, что после применения очередной карточки пересчитать минимальную стоимость прохождения не так и просто. Поэтому эту задачу он поручил вам.

Входные данные

В первой строке входных данных дано целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество клеток.

Во второй строке через пробел даны $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_1, \ldots, a_n \le 10^9$$$) — стоимости посещения клеток.

В третьей строке через пробел даны $$$n - 1$$$ целых чисел $$$b_i$$$ ($$$1 \le b_i \le n - i$$$) — числа, записанные на карточках.

В четвертой строке дано целое число $$$1 \le q \le n - 1$$$ — количество карточек, которые применит Федот.

В пятой строке через пробел даны $$$q$$$ уникальных целых чисел $$$c_i$$$ ($$$1 \le c_1, \ldots, c_q \le n - 1$$$; $$$c_i \neq c_j$$$ для $$$1 \le i \neq j \le q$$$) — номера карточек, которые последовательно применит Федот.

Выходные данные

Требуется вывести $$$q$$$ строк. В $$$k$$$-й строке ($$$1 \le k \le q$$$) должна быть выведена минимальная стоимость прохождения уровня после применения карточек с номерами $$$c_1, \ldots, c_k$$$.

ПримерВходные данные

4
1 10 100 1000
2 2 1
3
2 1 3

Выходные данные

1011
1101
1101

Примечание

Рассмотрим детально тестовый пример:

• Изначально путь пролегает через $$$4$$$ клетки $$$1$$$ - $$$2$$$ - $$$3$$$ - $$$4$$$ со стоимостями $$$1$$$, $$$10$$$, $$$100$$$, $$$1000$$$ соответственно  — суммарная стоимость получается равной $$$1111$$$. Обратите внимание, что данную стоимость выводить $$$\textbf{не нужно}$$$.
• Далее Федот применяет карточку $$$2$$$, после чего c клетки $$$2$$$ прыжок переносит сразу на клетку $$$2 + 2 = 4$$$ (так как на карточке было написано число $$$2$$$). В получившейся конфигурации путь пролегает через клетки $$$1$$$ - $$$2$$$ - $$$4$$$, а его стоимость соответственно равна $$$1011$$$.
• Следующим действием применяется карточка $$$1$$$, что продлевает прыжок с клетки $$$1$$$ сразу на клетку $$$1 + 2 = 3$$$ (так как на карточке аналогично было написано число $$$2$$$). В новой схеме уровня путь пролегает уже через клетки $$$1$$$ - $$$3$$$ - $$$4$$$, а его стоимость равна $$$1101$$$.
• Последней карточкой применяется $$$3$$$-я. Но так как она была равна $$$1$$$, то прыжок с клетки $$$3$$$ не изменился и до сих пор ведет на клетку $$$3 + 1 = 4$$$. Стоимость пути тоже не изменилась и составляет $$$1101$$$.