Farmer John ha $N$ pile di balle di fieno ($1 \leq N \leq 5 \cdot 10^5$), dove la $i$-esima pila contiene $a_i$ balle ($1 \leq a_i \leq 10^9$). Vuole rimuoverle tutte e dispone di $M$ ($1 \leq M \leq 2500$) mucche che possono aiutarlo. Se ingaggiata, la $i$-esima mucca ripeterà la seguente operazione $s_i$ volte ($1 \leq s_i \leq 100$) al costo di $c_i$ ($1 \leq c_i \leq 10^9$):

• Se la pila contiene almeno $p_i$ balle ($1 \leq p_i \leq 10^9$), la mucca rimuove una balla.
• Se la pila contiene meno di $p_i$ balle, la mucca non fa nulla.

Per ogni pila, FJ vuole rimuovere tutte le balle. Ingaggerà mucche in successione (anche la stessa mucca più volte) fino a svuotare la pila. Aiuta FJ a determinare il costo minimo per svuotare ogni pila.

Input

L’input arriva dal terminale / stdin.

La prima riga contiene $T$ ($1\le T\le 100$), il numero di test indipendenti. Ogni test ha il seguente formato:

La prima riga contiene un intero $N$. La seconda contiene $N$ interi, $a_1, a_2, \dots, a_N$.

La terza riga contiene un intero $M$. Le successive $M$ righe contengono $p_i, s_i, c_i$.

È garantito che le mucche possano rimuovere tutte le balle da ogni pila. Inoltre, la somma di $N$ su tutti i test non supera $5\cdot 10^5$ e la somma di $M$ non supera $2500$.

Output

Stampare l’output sul terminale / stdout.

Per ogni test, stampa $N$ interi separati da spazi: il $i$-esimo intero è il costo per rimuovere tutte le balle dalla $i$-esima pila.

Esempi

Input 1

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

Output 1

29 155 21
73 328 50

Spiegazione

Primo test: Per l’ultima pila, inizialmente di dimensione $10$, possiamo ingaggiare la mucca $3$ una volta, spendendo $5$ e rimuovendo due balle (non tre, perché dopo aver rimosso la seconda rimangono $8$ balle). Poi possiamo ingaggiare la mucca $2$ due volte, rimuovendo le $8$ balle senza lasciarne alcuna. Il costo totale è $ 5+8+8=21$.

Secondo test: Soddisfa $\max(s)=1$.

Punteggio

• Input 2-3: $a_i \le 100$
• Input 4-5: $\max(s)=1$
• Input 6-9: $\max(s)\le 4$
• Input 10-15: $\max(s)\le 20$
• Input 16-21: Nessun vincolo aggiuntivo.

Autore del problema: Sujay Konda