== include(page="template/taskheader" task_id="easyvect") ==

Poveste şi cerinţă...

Comisia AGM mai avea nevoie de o problema usoara. Stiind ca Elf nu a fost in stare sa treaca de OJI, se gandesc sa-i dea lui responsabilitatea. El stie cel mai bine vectori din toata informatica, asa ca se gandeste sa dea o problema usoara cu ei.
 
Aveti un vector $a$ cu $n$ elemente $pozitive$ si $q$ query-uri. Un query este dat de un numar $x$. Initial porniti din pozitia 1 a vectorului. Trebuie sa va plimbati $x$ unitati de timp. Din pozitia 1, puteti ajunge doar in pozitia 2. Din pozitia $n$, puteti ajunge doar in pozitia $n - 1$. Altfel, din pozitia $i$ se poate ajunge atat in pozitia $i - 1$, cat si in pozitia $i + 1$. Cand Elf este intr-o casuta, el aduna in sacul de valoare numarul scris acolo. Care este suma maxima pe care-o poate obtine dupa $x$ timp? Si numarul aflat pe pozitia 1 intra in tolba de valoare!

h2. Date de intrare

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 10^5$
* $1 ≤ q ≤ 10^5$
* $1 ≤ a_i ≤ 10^5$
* $1 ≤ x; 10^9$, pentru fiecare query din cele $q$
* **Atentie!** Rezultatul poate depasi numere pe 32 de biti.

h2. Exemplu