Bessie 在过去的 M 天（2≤M≤10$^9$）内参加了 N 次（1≤N≤10$^5$）挤奶。然而，她不太记得她是什么时候参加每次挤奶了。对于每次挤奶i=1…N，她知道这次挤奶的时间不早于第 S$_i$ 天（1≤S$_i$≤M）。此外，Bessie 记得 C 件事，每一件可以用一个三元组 (a,b,x) 表示，表示她记得第 b 次挤奶在第 a 次挤奶之后至少 x 天。

请帮助 Bessie 计算每次挤奶最早可能的日期。保证 Bessie 没有记错；换而言之，存在一种在范围1…M 内的挤奶时间的安排能够满足她的所有记忆。

测试点性质：

• 测试点 2-4 满足 N,C≤10$^3$。
• 测试点 5-10 没有额外限制。

输入格式（文件名：timeline.in）：

输入的第一行包含 N、M 和 C。下一行包含N 个空格分隔的整数 S$_1$,S$_2$,…,S$_N$。每个数均在范围 1…M 之内。

以下C 行每行包含三个整数 a、b 和x，表示第 b 次挤奶在第 a 次挤奶之后至少 x 天。对于每一行，a≠b，a 和 b 在范围 1…N 内，且 x 在范围 1…M 内。

输出格式（文件名：timeline.out）：

输出 N 行，为每次挤奶最早可能的日期。

输入样例：

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

输出样例：

1
6
3
8

第二次挤奶发生在第一次挤奶之后至少五天，所以它不可能发生在第 1+5=6 天前。第四次挤奶发生在第二次挤奶之后至少两天，所以它不可能发生在第 6+2=8 天前。