Timeline

Bessie attended $n$ milking sessions over the past $m$ days. However, she is having trouble remembering when she attended each session.

For each session $i=\mathrm{1...}n$, she knows that it occurred no earlier than day $s_i$. Additionally, Bessie has $c$ memories, each described by a triple $(a,b,x)$, where she recalls that session $b$ happened at least $x$ days after $a$.

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 $\mathrm{1...}m$ such that all constraints from her memories are satisfied.

Input

The first line of input contains $n(1\le n\le 10^5)$, $m(2\le m\le 10^9)$, and $c(1\le c\le 10^5)$. The next line contains $n$ integers $s_1,s_2,...,s_n(1\le s_i\le m)$. Each is in the range $\mathrm{1...}m$.

The next $c$ lines contain three integers $a,b$ and $x$ indicating that session $b$ happened at least $x$ days after $a$. For each line $a\ne b,a$ and $b$ are in the range $\mathrm{1...}n$, and $x$ is in the range $\mathrm{1...}m$.

Output

Print $n$ lines giving the earliest possible date of occurrence for each session.

Examples

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