Benvenuti al TV Time di Mr. Ant Tenna! In questo round del gioco ti vengono dati $n$ secchi, dove l'$i$-esimo secchio ha una capacità massima di $v_i$ volumi d'acqua. All'inizio del gioco tutti i secchi verranno riempiti completamente d'acqua, e la tua missione è trattenerne il più possibile per i successivi $t$ secondi. Ma ecco il colpo di scena: questi secchi sono bucati! L'$i$-esimo secchio ha una velocità di perdita pari a $l_i$, il che significa che ogni secondo dopo l'inizio del gioco l'$i$-esimo secchio perde $l_i$ volumi d'acqua.
Prima che il gioco inizi, puoi fondere un numero qualsiasi di secchi in uno solo. Il secchio risultante ha una capacità uguale alla capacità massima tra i secchi fusi e una velocità di perdita uguale alla velocità di perdita minima tra i secchi fusi. Puoi effettuare fusioni un numero arbitrario di volte, ma devono essere eseguite prima di versare qualsiasi quantità d'acqua.
Tenna pone $q$ domande, dove l'$i$-esima domanda ha un limite di tempo $t_i$. Per ogni $1 \le i \le q$, calcola il massimo volume totale trattenuto dopo $t_i$ secondi. Nota che ogni domanda è indipendente.
Dati di ingresso
Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 5 \times 10^4$) che indica il numero di casi di test. Per ciascun caso di test:
La prima riga contiene un intero $n$ ($1 \le n \le 2 \times 10^5$), che indica il numero di secchi.
La seconda riga contiene $n$ interi $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), dove $v_i$ è la capacità dell'$i$-esimo secchio.
La terza riga contiene $n$ interi $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), dove $l_i$ è la velocità di perdita dell'$i$-esimo secchio.
La quarta riga contiene un intero $q$ ($1 \le q \le 2 \times 10^5$), che indica il numero di domande.
La quinta riga contiene $q$ interi $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), dove $t_i$ è il limite di tempo per l'$i$-esima query.
È garantito che né la somma di $n$ né la somma di $q$ su tutti i casi di test supererà $2 \times 10^5$.
Dati di uscita
Per ciascun caso di test, stampa una riga contenente $q$ interi separati da uno spazio, dove l'$i$-esimo intero è il massimo volume totale trattenuto dopo $t_i$ secondi.
Esempi
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