时间限制：1秒　　内存限制：256M

---

【问题描述】

　　这个快乐而又漫长的暑假共 \(M\) 天的时间，小H的在这个假期里一共参加了 \(N\) 次社区活动。假期结束了，学校要求填写加器社区活动的时间表，但他却已经忘了每次社区活动是在哪个时候了。

　　对于第 \(i\) 次社区活动，小H还记得是不早于第 \(S_i\) 天进行的。另外，她还有 \(K\) 条记录，每条形如一个三元组 \((A,B,X)\)，表示第 \(B\) 次社区活动在第 \(A\) 次社区活动结束至少 \(X\) 天后进行的。

　　现在请你帮小H算出在满足所有条件的前提下，每次社区活动的最早日期。

【输入格式】

　　输入的第一行为三个整数 \(N,M,K\)。保证 \(1 \leq N,K \leq 10^5\)，\(2 \leq M \leq 10^9\)。接下来一行包含 \(N\) 个整数 \(S_1, S_2 , \ldots, S_N\)，保证 \(\forall 1 \leq i \leq N\)，都满足 \(1 \leq S_i \leq M\)。最后的 \(K\) 行每行三个整数 \(A,B,X\)，描述一条记录。保证 \(A \neq B\)，且 \(1 \leq X \leq M\)。
　　输入保证小H 记录没有错误，这意味着一定存在一种合法的方案。

【输出格式】

　　输出 \(N\) 行，每行一个整数，第 \(i\) 行的数表示第 \(i\) 次社区活动的最早日期。

【输入输出样例】

　Input

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

　Output

1
6
3
8

【数据说明】

　　- 测试点 \(2 \sim 4\) 满足 \(N,C \leq 10^3\)。
　　- 测试点 \(5 \sim 10\) 没有特殊限制。

【来源】

　　Mr.he