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 = 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 $1 ... m$ such that all constraints from her memories are satisfied. \InputFile 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 $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 $1 ... n$, and $x$ is in the range $1 ... m$. \OutputFile 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$.