Timeline

문제

Bessie attended $NN$ milking sessions ($1\le N\le {10}^{5}1\backslash le\; N\backslash le\; 10^5$) over the past $MM$ days ($2\le M\le {10}^{9}2\; \backslash le\; M\; \backslash le\; 10^9$). However, she is having trouble remembering when she attended each session.

For each session $i=1\dots Ni\; =\; 1\; \backslash ldots\; N$, she knows that it occurred no earlier than day $S_{i}S\_i$ ($1\le S_i\le M1\backslash le\; S\_i\backslash le\; M$). Additionally, Bessie has $CC$ memories ($1\le C\le {10}^{5}1\backslash le\; C\backslash le\; 10^5$), each described by a triple $(a,b,x)(a,b,x)$, where she recalls that session $bb$ happened at least $xx$ days after $aa$.

Help Bessie by computing the earliest possible date of occurrence for each milking session. It is guaranteed that Bessie did not remember incorrectly; in other words, there exists an assignment of sessions to days in the range $1\dots M1\backslash ldots\; M$ such that all constraints from her memories are satisfied.

입력

The first line of input contains $NN$, $MM$, and $CC$.

The next line contains $NN$ space-separated integers $S_1,S_2,\dots ,S_{N}S\_1,S\_2,\backslash ldots,\; S\_N$. Each is in the range $1\dots M1\; \backslash ldots\; M$.

The next $CC$ lines contain three integers, $aa$, $bb$, and $xx$ indicating that session $bb$ happened at least $xx$ days after $aa$. For each line, $a\mathrm{\ne }ba\; \backslash neq\; b$, $aa$ and $bb$ are in the range $1\dots N1\; \backslash ldots\; N$, and $xx$ is in the range $1\dots M1\; \backslash ldots\; M$.

출력

Output $NN$ lines giving the earliest possible date of occurrence for each session.

힌트

Session two occurred at least five days after session one, so it cannot have occurred before day $1+5=6.1+5=6.$ Session four occurred at least two days after session two, so it cannot have occurred before day $6+2=86+2=8$.

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

1
6
3
8