Problem 1. Timeline

USACO 2020 February Contest, Gold

Bessie 在过去的 $M$ 天（$2 \le M \le 10^9$）内参加了 $N$ 次（$1\le N\le 10^5$）挤奶。然而，她不太记得她是什么时候参加每次挤奶了。

对于每次挤奶 $i = 1 \ldots N$，她知道这次挤奶的时间不早于第 $S_i$ 天（$1\le S_i\le M$）。此外，Bessie 记得 $C$ 件事，每一件可以用一个三元组 $(a,b,x)$ 表示，表示她记得第 $b$ 次挤奶在第 $a$ 次挤奶之后至少 $x$ 天。

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

测试点性质： 测试点 2-4 满足 $N,C \le 10^3$。测试点 5-10 没有额外限制。

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

输入的第一行包含 $N$、$M$ 和 $C$。

下一行包含 $N$ 个空格分隔的整数 $S_1,S_2,\ldots, S_N$。每个数均在范围 $1 \ldots M$ 之内。

以下 $C$ 行每行包含三个整数 $a$、$b$ 和 $x$，表示第 $b$ 次挤奶在第 $a$ 次挤奶之后至少 $x$ 天。对于每一行，$a \neq b$，$a$ 和 $b$ 在范围 $1 \ldots N$ 内，且 $x$ 在范围 $1 \ldots 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$ 天前。

供题：Mark Gordon