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

Tanarul nobil Naelav doreste sa cucereasca inima prea frumoasei si priceputei Adnana, fata regelui Arpsod, stapanul regatului Valores. El se gandeste sa o impresioneze facand niste armuri cu totul si cu totul din haur pentru dragonii ei. Tatal sau refuza insa sa cheltuiasca atat de multi bani pentru o pasiune adolescentina asa ca Naelav paraseste regatul amenintand oamenii cu catapulta sa, care arunca blaturi tari ca piatra.
Regatul Valores este alcatuit din N orase dispuse in linie. Astfel din orasul $i$ se poate ajunge in orasele $i+1$ si $i-1$, exceptie facand orasele $1$ si $N$. Urmeaza o lunga serie de $x$ episoade. In fiecare episod, Naelav asediaza un anume oras $i$, sustrage din visteria acestuia $v[~i~]$ monezi de haur si porneste catre unul din orasele adiacente. El poate ataca un oras de mai multe ori pentru aceeasi suma, dar nu in episoade consecutive. Stim ca primul oras ce a fost deja asediat este chiar orasul sau natal, orasul cu numarul $1$.
Pentru a putea da cat mai multe spoilere prietenilor tai, te gandesti sa aflii care ar fi valoarea maxima pe care ar putea-o colecta Naelav in urmatoarele $x$ episoade, in $Q$ astfel de scenarii.

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

Fişierul de intrare $easyvect.in$ contine pe prima linie numarul $T$, numarul de teste. Fiecare test va contine numerele $N$ si $Q$ numarul de orase, respectiv numarul de intrebari si un sir de $N$ numere pe linia urmatoare, reprezentand cantitatea de monezi care se pot obtine $v[~i~]$ din fiecare oras intr-un episod. Pe urmatoarele $Q$ linii sunt descrise numerele $x$, reprezentand numarul de episoade pe care le-ar putea avea serialul.

Fişierul de intrare $easyvect.in$ contine pe prima linie numerele n si q. Pe urmatoarele q linii sunt descrise numerele x, corespunzatoare query-urilor.

h2. Date de ieşire

În fişierul de iesire $easyvect.out$ se vor afisa $T*Q$ linii, cate una pentru fiecare query.
 

În fişierul de ieşire $easyvect.out$ se vor afisa q linii, cate una pentru fiecare query.

h2. Restricţii

* $1 ≤ T ≤ 10$
* $2 ≤ N ≤ 10^5$
* $1 ≤ Q ≤ 10^5$
* $1 ≤ v[~i~] ≤ 10^5$
* $1 ≤ x ≤ 10^9$, pentru fiecare query din cele $Q$

* $2 ≤ 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.

* Naelav este mai mult taran decat nobil
* Suparat ca nu o poate cuceri pe Adnana, Naelav se inchide in camera sa si se joaca cu dragonul sau micut.

h2. Exemplu