Askhat es un empresario en potencia. Rápidamente se dio cuenta de que la programación es un negocio poco rentable, por lo que decidió abrir una granja de pollos.

Su granja consta de $n$ pollos ordenados en una fila. El $i$-ésimo pollo puede comer como máximo $a_i$ granos. Hay $m$ comederos, cada uno descrito por los enteros $l_j, r_j, c_j$. El $j$-ésimo comedero puede alimentar al $i$-ésimo pollo si $l_j \le i \le r_j$, y hay $c_j$ granos en este comedero.

Resulta que todo negocio tiene sus dificultades; en este caso, tiene la cara del control de alimentación de pollos, representado por Ildar. Él afirma que toda granja de pollos respetable debe tener un pollo representante. Es decir, debe existir un pollo $i$ tal que $l_j \le i \le r_j$ se cumpla para todo comedero $j$. Todos los comederos que no obedezcan esta regla deben ser eliminados.

Ahora, Askhat te pide que encuentres, para cada $i$, cuál es el número máximo de granos que se pueden dar a los pollos si dejamos solo los comederos que pueden alimentar al pollo $i$.

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 10^4$) — el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n, m$ ($1 \le n, m \le 10^5$) — el número de pollos y el número de comederos, respectivamente.

La siguiente línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — el número de granos que los pollos pueden comer.

Cada una de las siguientes $m$ líneas contiene tres enteros $l_j, r_j, c_j$ ($1 \le l_j \le r_j \le n, 0 \le c_j \le 10^9$) — la descripción del $j$-ésimo comedero.

Se garantiza que tanto la suma de $n$ como la suma de $m$ para todos los casos de prueba no exceden $10^5$.

Salida

Para cada caso de prueba, imprime $n$ enteros — la respuesta al problema.

Ejemplos

Entrada 1

1
4 3
3 3 2 2
1 2 2
3 3 3
2 2 4

Salida 1

2 5 2 0