El granjero John tiene ~N~ pilas de pacas de heno, donde la i-ésima pila contiene ~a_i~ pacas. Quiere retirar todas estas pacas y dispone de ~M~ ~(1 \leq M \leq 2500)~ vacas para ayudarle. Si se contrata a la i-ésima vaca, esta repetirá la siguiente acción ~s_i~ veces por un coste de ~c_i~:

• Si la pila contiene al menos ~p_i~ pacas, la vaca retirará una paca.
• Si la pila contiene menos de pi pacas, la vaca no hará nada.

Para cada pila, FJ quiere retirar todas las balas de heno. Lo hará contratando vacas en secuencia (posiblemente la misma vaca más de una vez) hasta que la pila quede vacía. Ayuda a FJ a determinar el coste mínimo para vaciar cada pila.

Entrada

La primera línea contiene ~T~, 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, ..., a_N~.
• La tercera línea contiene un entero ~M~. Las siguientes ~M~ líneas contendrán ~p_i, s_i, c_i~.

Se garantiza que las vacas podrán retirar todas las balas de heno de cada pila. Además, se garantiza que la suma de N en todas las pruebas no supera ~5 \cdot 10^5~, y la suma de ~M~ en todas las pruebas no supera 2500.

Salida

Para cada prueba, imprimir ~N~ enteros separados por espacios, donde el i-ésimo entero representa el costo de retirar todas las balas de heno de la i-ésima pila.

Restricciones

• ~1 \leq N \leq 5 \cdot 10^5~
• ~1 \leq a_i \leq 10^9~
• ~1 \leq s_i \leq 100~
• ~1 \leq c_i \leq 10^9~
• ~1 \leq p_i \leq 10^9~
• ~1 \leq T \leq 100~

Puntuación

Entradas	Restricciones adicionales
2-3	~a_i \leq 100~
4-5	~max(s) = 1~
6-9	~max(s) \leq 4~
10-15	~max(s) \leq 20~
16-21	Sin restricciones adicionales

Ejemplo de Entrada

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

Ejemplo de Salida

29 155 21
73 328 50

Primera prueba: Para la última pila de tamaño inicial 10, podemos contratar a la vaca 3 una vez, lo que cuesta 5 y eliminará dos fardos de heno (no tres, ya que el número de fardos de heno se convierte en 8 después de eliminar el segundo). Luego podemos contratar a la vaca 2 dos veces, eliminando los 8 fardos de heno, lo que resulta en que no queden fardos. El costo total es ~5+8+8=21~.

Segunda prueba: Esto satisface ~max(s)=1~.