Velkomin í TV Time hjá Mr. Ant Tenna! Í þessari umferð leiksins færðu $n$ fötur, þar sem $i$-ta fatan hefur hámarksrúmmál upp á $v_i$ rúmmálseiningar af vatni. Í upphafi leiksins verða allar föturnar fylltar alveg af vatni og verkefni þitt er að halda eins miklu vatni og þú getur í þeim næstu $t$ sekúndurnar. En hér kemur fléttan: þessar fötur eru bilaðar! $i$-ta fatan er með lekahraða $l_i$, sem þýðir að á hverri sekúndu eftir að leikurinn hefst leka $l_i$ rúmmálseiningar af vatni úr $i$-tu fötunni.
Áður en leikurinn hefst máttu sameina hvaða fjölda af fötum sem er í eina. Fatan sem verður til hefur rúmmál sem jafngildir mesta rúmmálinu meðal sameinuðu fatanna og lekahraða sem jafngildir minnsta lekahraðanum meðal sameinuðu fatanna. Þú getur framkvæmt sameiningar eins oft og þú vilt, en þær verða að fara fram áður en vatni er hellt í.
Tenna leggur fram $q$ spurningar, þar sem $i$-ta spurningin hefur tímamörk $t_i$. Fyrir hvert $1 \le i \le q$ skaltu reikna mesta mögulega heildarrúmmál vatns sem eftir er eftir $t_i$ sekúndur. Athugaðu að hver spurning er óháð hinum.
Inntak
Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 5 \times 10^4$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:
Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2 \times 10^5$), sem gefur til kynna fjölda fata.
Önnur línan inniheldur $n$ heiltölur $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), þar sem $v_i$ er rúmmál $i$-tu fötunnar.
Þriðja línan inniheldur $n$ heiltölur $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), þar sem $l_i$ er lekahraði $i$-tu fötunnar.
Fjórða línan inniheldur heiltölu $q$ ($1 \le q \le 2 \times 10^5$), sem gefur til kynna fjölda spurninga.
Fimmta línan inniheldur $q$ heiltölur $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), þar sem $t_i$ eru tímamörkin fyrir $i$-tu fyrirspurnina.
Það er tryggt að hvorki summa $n$ né summa $q$ yfir öll prófunartilvik fari yfir $2 \times 10^5$.
Úttak
Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $q$ heiltölur aðskildar með bili, þar sem $i$-ta heiltalan er mesta mögulega heildarrúmmál sem eftir er eftir $t_i$ sekúndur.
Dæmi
2
4
5 4 7 6
2 1 3 2
3
3 1 2
4
19 47 21 13
5 14 2 3
5
5 2 6 1 4
4 14 8
43 67 38 77 48