Tervetuloa Mr. Ant Tennan TV Time -ohjelmaan! Tällä pelikierroksella sinulle annetaan $n$ ämpäriä, joista $i$:nnen ämpärin enimmäistilavuus on $v_i$ tilavuusyksikköä vettä. Pelin alussa kaikki ämpärit täytetään piripintaan vedellä, ja tehtäväsi on pitää mahdollisimman paljon vettä talletettuna seuraavien $t$ sekunnin ajan. Mutta tässä on juonenkäänne: nämä ämpärit ovat rikki! $i$:nnellä ämpärillä on vuotonopeus $l_i$, mikä tarkoittaa, että joka sekunti pelin alkamisen jälkeen $i$:nnestä ämpäristä valuu pois $l_i$ tilavuusyksikköä vettä.
Ennen pelin alkua voit yhdistää minkä tahansa määrän ämpäreitä yhdeksi. Tuloksena syntyvän ämpärin tilavuus on yhtä suuri kuin yhdistettyjen ämpäreiden suurin tilavuus, ja sen vuotonopeus on yhtä suuri kuin yhdistettyjen ämpäreiden pienin vuotonopeus. Voit tehdä yhdistämisiä mielivaltaisen monta kertaa, mutta ne on suoritettava ennen veden täyttämistä.
Tenna esittää $q$ kysymystä, joista $i$:nnellä kysymyksellä on aikaraja $t_i$. Laske jokaiselle $1 \le i \le q$ suurin mahdollinen jäljellä oleva kokonaistilavuus $t_i$ sekunnin kuluttua. Huomaa, että jokainen kysymys on riippumaton muista.
Syöte
Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 5 \times 10^4$), joka ilmaisee testitapausten määrän. Jokaisessa testitapauksessa:
Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \times 10^5$), joka ilmaisee ämpäreiden määrän.
Toinen rivi sisältää $n$ kokonaislukua $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), missä $v_i$ on $i$:nnen ämpärin tilavuus.
Kolmas rivi sisältää $n$ kokonaislukua $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), missä $l_i$ on $i$:nnen ämpärin vuotonopeus.
Neljäs rivi sisältää kokonaisluvun $q$ ($1 \le q \le 2 \times 10^5$), joka ilmaisee kysymysten määrän.
Viides rivi sisältää $q$ kokonaislukua $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), missä $t_i$ on $i$:nnen kyselyn aikaraja.
On taattu, että lukujen $n$ summa eikä lukujen $q$ summa yli kaikkien testitapausten ylitä arvoa $2 \times 10^5$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää $q$ välilyönnillä erotettua kokonaislukua, missä $i$:s kokonaisluku on suurin mahdollinen jäljellä oleva kokonaistilavuus $t_i$ sekunnin kuluttua.
Esimerkit
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