该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

歌手贝丝在过去的 M 天内要完成 了 N 场巡回演唱会，但她忘记了每场演出的具体日期。已知： 第 i 场演唱会不能早于第 Si天举办； 她还有 C 条行程记录，每条记录形如 (a,b,x)，表示第 b 场演唱会必须在第 a 场结束至少 x 天后举行。 请帮贝丝确定每场演唱会的最早举办日期，满足所有时间约束且不超过第 M 天。

输入格式：

第一行三个整数 N,M,C。保证 1≤N,C≤10^5，2≤M≤10^9。 接下来一行包含 N 个整数 Si,保证Si都满足 1≤Si ≤M。 下面 C 行每行三个整数 a,b,x，描述一条行程记录。保证 a!=b，且 1≤x≤M。

输出格式：

输出 N 行，每行一个整数，第 i 行的数表示第 i 场演唱会的最早日期。

样例：

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

1
6
3
8

提示