El granjero John tiene $N$ pilas de pacas de heno ($1 \leq N \leq 5 \cdot 10^5$), donde la $i$-ésima pila contiene $a_i$ pacas ($1 \leq a_i \leq 10^9$). Él desea retirar todas estas pacas y tiene $M$ ($1 \leq M \leq 2500$) vacas disponibles para ayudarlo. Si es contratada, la $i$-ésima vaca repetirá lo siguiente $s_i$ veces ($1 \leq s_i \leq 100$) por un costo de $c_i$ ($1 \leq c_i \leq 10^9$):

• Si la pila contiene al menos $p_i$ pacas ($1 \leq p_i \leq 10^9$), entonces la vaca retirará una paca.
• Si la pila contiene menos de $p_i$ pacas, la vaca no hace nada.

Para cada pila, FJ desea retirar todas las pacas que contiene. Lo hará contratando vacas en secuencia (posiblemente la misma vaca más de una vez) hasta que la pila quede vacía. Ayude a FJ a determinar el costo mínimo para vaciar cada pila.

Entrada

La primera línea contiene $T$ ($1 \le T \le 100$), el número de casos de prueba independientes. Cada caso de prueba tiene el siguiente formato:

La primera línea contiene un entero $N$. La segunda línea contiene $N$ enteros, $a_1, a_2, \dots, a_N$.

La tercera línea contiene un entero $M$. Luego, las siguientes $M$ líneas contienen $p_i, s_i, c_i$.

Se garantiza que las vacas serán capaces de retirar todas las pacas de cada pila. Además, se garantiza que la suma de $N$ sobre todos los casos de prueba no excede $5\cdot 10^5$, y la suma de $M$ sobre todos los casos de prueba no excede $2500$.

Salida

Para cada caso de prueba, imprima $N$ enteros separados por espacios, donde el $i$-ésimo entero es el costo de retirar todas las pacas de la $i$-ésima pila.

Ejemplos

Entrada 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

Salida 1

29 155 21
73 328 50

Nota

Primer caso de prueba: Para la última pila de tamaño inicial $10$, podemos contratar a la vaca $3$ una vez, lo cual cuesta $5$ y retirará pacas dos veces (no tres, porque el número de pacas se convierte en $8$ después de retirar la segunda). Luego podemos contratar a la vaca $2$ dos veces, retirando las $8$ pacas restantes, resultando en cero pacas. El costo total es $5+8+8=21$.

Segundo caso de prueba: Este satisface $\max(s)=1$.

Subtareas

• Entradas 2-3: $a_i \le 100$
• Entradas 4-5: $\max(s)=1$
• Entradas 6-9: $\max(s)\le 4$
• Entradas 10-15: $\max(s)\le 20$
• Entradas 16-21: Sin restricciones adicionales.