### 问题描述

小齐参加了 $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$。