Farmer John tiene $N$ montones de pacas de heno ($1 \leq N \leq 5 \cdot 10^5$), donde el $i$-ésimo montón contiene $a_i$ pacas de heno ($1 \leq a_i \leq 10^9$). Quiere retirar todas estas pacas de heno y tiene $M$ ($1 \leq M \leq 2500$) vacas disponibles para ayudarlo. Si se la contrata, 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 el montón contiene al menos $p_i$ pacas de heno ($1 \leq p_i \leq 10^9$), entonces la vaca retirará una paca de heno.
• Si el montón contiene menos de $p_i$ pacas de heno, la vaca no hace nada.

Para cada montón, FJ quiere retirar todas las pacas de heno que contiene. Lo hará contratando vacas en secuencia (posiblemente la misma vaca más de una vez) hasta que el montón quede vacío. Ayuda a FJ a determinar, para cada montón, el costo mínimo de vaciarlo.

Entrada

La entrada llega desde el terminal / stdin.

La primera línea contiene $T$ ($1\le T\le 100$), el número de pruebas independientes. Cada 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 contendrán $p_i, s_i, c_i$.

Se garantiza que las vacas podrán retirar todas las pacas de heno de cada montón. Además, se garantiza que la suma de $N$ sobre todas las pruebas no supera $5\cdot 10^5$, y que la suma de $M$ sobre todas las pruebas no supera $2500$.

Salida

Imprime la salida en el terminal / stdout.

Para cada prueba, imprime $N$ enteros separados por espacios, donde el $i$-ésimo entero es el costo de retirar todas las pacas de heno del $i$-ésimo montón.

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

Primera prueba: Para el último montón de tamaño inicial $10$, podemos contratar a la vaca $3$ una vez, lo que cuesta $5$ y retirará pacas de heno dos veces (no tres porque el número de pacas de heno pasa a $8$ después de que se retire la segunda). Luego podemos contratar a la vaca $2$ dos veces, retirando las $8$ pacas de heno, sin que quede ninguna paca de heno. El costo total es $ 5+8+8=21$.

Segunda prueba: Esto 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.

Créditos del problema: Sujay Konda