Timeline

题目描述:

Bessie 在过去的 M 天（2≤M≤10⁹）内参加了 N 次（1≤N≤10⁵）挤奶。然而，她不太记得她是什么时候参加每次挤奶了。

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

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

测试点性质：

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

输入格式:

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

下一行包含 N 个空格分隔的整数 S1,S2,…,SN。每个数均在范围 1…M 之内。

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

输出格式:

输出 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 天前。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2020 FEB Gold