### 问题描述 小齐参加了 $N$ 次挤奶活动，这些活动发生在过去的 $M$ 天中。然而，她现在有些困惑，不记得每次活动发生的具体日期了。 对于每一次活动 $i=1 \ldots N$，她知道它发生的最早日期不早于第 $S_i$ 天。此外，小齐还有 $C$ 个记忆，每个记忆由三元组 $(a, b, x)$ 描述，其中她记得第 $b$ 次活动至少在第 $x$ 天后的某一天发生，而第 $a$ 次活动已经发生。 帮助小齐计算每次挤奶活动的可能最早日期。保证小齐没有错误记忆，也就是说，存在一种活动安排方式，满足所有记忆的约束条件。 ### 输入格式 第一行输入 $N$、$M$ 和 $C$。 接下来一行包含 $N$ 个空格分隔的整数 $S_1, S_2, \ldots, S_N$，每个数字在 $1 \ldots M$ 范围内。 接下来的 $C$ 行，每行包含三个整数 $a, b, x$，表示第 $b$ 次活动至少在第 $x$ 天后的某一天发生，而第 $a$ 次活动已经发生。对于每一行，$a \neq b$，$a$ 和 $b$ 在 $1 \ldots N$ 范围内，$x$ 在 $1 \ldots M$ 范围内。 ### 输出格式 输出 $N$ 行，给出每次挤奶活动的可能最早日期。 ### 样例输入 ``` 4 10 3 1 2 3 4 1 2 5 2 4 2 3 4 4 ``` ### 样例输出 ``` 1 6 3 8 ``` ### 评测数据规模 $1 \leq N \leq 10^5$，$2 \leq M \leq 10^9$，$1 \leq S_i \leq M$，$1 \leq C \leq 10^5$。