题目描述

小 $A$ 是一位酷爱旅行的旅游达人，每年都会周游世界各地的名山大川。

今年小 $A$ 的旅行格外精彩，他在 $M$ 天内，游览了 $N$ 个不同的城市（编号 $1 \sim N$），小 $A$ 想要根据自己今年精彩的旅游经历，写一本旅行日记，由于他之前没有做记录的习惯，现在他在努力的回忆每个城市是本次旅行第几天到达的。

虽然他已经不能确切的回忆出每个城市是第几天到达的，但是经过他的推测，可以确定，编号为 $i$ 的城市，一定不早于第 $A_i$ 天到达。

另外，根据他的各项买票记录，他还推测出了 $T$ 条关键线索，第 $j$ 条线索显示，编号为 $Y_j$ 的城市，是在到达编号为 $X_j$ 的城市之后的至少 $C_j$ 天后到达的。

可以确定的是，小 $A$ 提供的数据一定是正确的，请根据小 $A$ 提供的数据，编程帮助小 $A$ 计算出，他最早是在本次旅行的第几天，到达 $1 \sim N$ 的每个城市的。

输入格式

第 $1$ 行读入 $3$ 个整数 $N, M, T$。

第 $2$ 行读入 $N$ 个整数，$A_1, …, A_n$。

接下来的 $T$ 行，每行读入 $3$ 个整数，$X_j, Y_j, C_j$。

输出格式

输出 $N$ 行，每行一个整数，第 $i$ 行输出小 $A$ 最早是在本次旅行的第几天，到达 $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 \le 10^3$，$1 \le T \le 10^3$。

对于 $100\%$ 的数据，满足 $1 \le N, T \le 10^5$，$2 \le M \le 10^9$，$1 \le A_i \le M$，$X_j \neq Y_j$，$1 \le C_j \le M$。