Velkommen til Mr. Ant Tennas TV Time! I denne runden av spillet får du $n$ bøtter, der den $i$-te bøtten har en maksimal kapasitet på $v_i$ volumenheter vann. Ved starten av spillet fylles alle bøttene helt opp med vann, og oppdraget ditt er å holde på så mye vann som mulig i løpet av de neste $t$ sekundene. Men her er tvisten: disse bøttene er ødelagte! Den $i$-te bøtten har en lekkasjehastighet på $l_i$, som betyr at hvert sekund etter at spillet starter, lekker det ut $l_i$ volumenheter vann fra den $i$-te bøtten.
Før spillet starter, kan du slå sammen et hvilket som helst antall bøtter til én. Den resulterende bøtten får en kapasitet lik den største kapasiteten blant de sammenslåtte bøttene, og en lekkasjehastighet lik den minste lekkasjehastigheten blant de sammenslåtte bøttene. Du kan utføre sammenslåinger så mange ganger du vil, men de må gjøres før det fylles i vann.
Tenna stiller $q$ spørsmål, der det $i$-te spørsmålet har en tidsgrense $t_i$. For hver $1 \le i \le q$, beregn det maksimale totale gjenværende volumet etter $t_i$ sekunder. Merk at hvert spørsmål er uavhengig.
Inndata
Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 5 \times 10^4$) som angir antall testtilfeller. For hvert testtilfelle:
Den første linjen inneholder et heltall $n$ ($1 \le n \le 2 \times 10^5$), som angir antall bøtter.
Den andre linjen inneholder $n$ heltall $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), der $v_i$ er kapasiteten til den $i$-te bøtten.
Den tredje linjen inneholder $n$ heltall $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), der $l_i$ er lekkasjehastigheten til den $i$-te bøtten.
Den fjerde linjen inneholder et heltall $q$ ($1 \le q \le 2 \times 10^5$), som angir antall spørsmål.
Den femte linjen inneholder $q$ heltall $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), der $t_i$ er tidsgrensen for den $i$-te spørringen.
Det er garantert at verken summen av $n$ eller summen av $q$ over alle testtilfeller vil overstige $2 \times 10^5$.
Utdata
For hvert testtilfelle skal du skrive ut én linje som inneholder $q$ heltall atskilt med mellomrom, der det $i$-te heltallet er det maksimale totale gjenværende volumet etter $t_i$ sekunder.
Eksempler
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