Bessie asistió a ~N~ sesiones de ordeño durante los últimos ~M~ días. Sin embargo, tiene dificultades para recordar cuándo asistió a cada sesión.

Para cada sesión ~i = 1...N~, sabe que ocurrió no antes del día ~S_i~. Además, Bessie tiene ~C~ recuerdos, cada uno descrito por una terna ~(a, b, x)~, donde recuerda que la sesión ~b~ ocurrió al menos ~x~ días después de la sesión ~a~.

Ayuda a Bessie calculando la fecha más temprana posible de ocurrencia para cada sesión de ordeño. Se garantiza que Bessie no recordó incorrectamente; es decir, existe una asignación de sesiones ~a~ días en el rango ~1...M~ tal que se cumplen todas las restricciones de sus recuerdos.

Entrada

La primera línea contiene ~N, M~ y ~C~.

La siguiente línea contiene ~N~ enteros separados por espacios: ~S_1, S_2, ..., S_N~. Cada entero está en el rango de ~1~ a ~M~.

Las siguientes ~C~ líneas contienen tres enteros: ~a, b~ y ~x~, que indican que la sesión ~b~ ocurrió al menos ~x~ días después de la sesión ~a~. En cada línea, ~a \neq b~, ~a~ y ~b~ están en el rango de ~1~ a ~N~, y ~x~ está en el rango de ~1~ a ~M~.

Salida

Genera ~N~ líneas que indican la fecha más temprana posible de ocurrencia para cada sesión.

Restricciones

• ~1 \leq N \leq 10^5~
• ~2 \leq M \leq 10^9~
• ~1 \leq S_i \leq M~
• ~1 \leq C \leq 10^5~

Ejemplo de Entrada

4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4

Ejemplo de Salida

1
6
3
8

La segunda sesión tuvo lugar al menos cinco días después de la primera, por lo que no pudo haber ocurrido antes del día ~1+5=6~. La cuarta sesión tuvo lugar al menos dos días después de la segunda, por lo que no pudo haber ocurrido antes del día ~6+2=8~.

USACO 2020 February Contest, Gold Problem 1. Timeline.