题目描述

小 A 在一次旅行中到达了 $n$ 座城市，城市编号为 $1$ 到 $n$，整个旅行不超过 $m$ 天。

根据回忆，他确定到达城市 $i$ 的日期不会早于第 $A_i$ 天。此外，还有 $t$ 条线索。第 $j$ 条线索包含 $X_j,Y_j,C_j$，表示到达城市 $Y_j$ 的日期至少比到达城市 $X_j$ 晚 $C_j$ 天。

所有线索一定可以同时满足。请计算每座城市最早可以在第几天到达。

输入格式

第一行包含三个整数 $n,m,t$，分别表示城市数量、旅行的总天数上限和线索数量。

第二行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$。

接下来 $t$ 行，每行包含三个整数 $X_j,Y_j,C_j$，表示一条线索。

输出格式

输出 $n$ 行，第 $i$ 行输出城市 $i$ 最早可能到达的日期。

样例

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

1
7
3
9
10

8 20 8
1 5 6 7 2 9 3 10
1 2 1
1 3 2
2 3 1
3 4 3
5 6 2
4 6 4
6 8 5
7 8 3

1
5
6
9
2
13
3
18

数据范围与提示

• 对于 $20\%$ 的数据，$1 \le n,t \le 10^3$
• 对于 $100\%$ 的数据，$1 \le n,t \le 10^5$，$2 \le m \le 10^9$
• $1 \le A_i \le m$
• $1 \le X_j,Y_j \le n$，$X_j \ne Y_j$
• $1 \le C_j \le m$
• 保证所有线索可以同时满足，且每座城市的最早到达日期不超过 $m$