小 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,\dots,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
小 A 在 10 天内共访问了 5 个城市。
1 号城市不早于 第 1 天到达。
\dots
5 号城市不早于 第 5 天到达。
有 4 条关键线索。
1 号城市可以在第 1 天到达，3 号城市可以在第 3 天到达。
根据 2 号城市在到达 1 号城市之后至少 6 天后到达，可知 2号城市可以在第 7 天到达。
根据 4 号城市在到达 2 号城市之后至少 2 天后到达，可知 4 号城市可以在第 9 天到达。
虽然根据第 3 条关键线索， 4 号城市在到达 3 号城市之后至少 4 天后到达，可以推测， 4 号城市可以在第 7 天到达，但结合第 2 条线索，显然在第 9 天到达才是合理的。
根据 5 号城市在到达 4 号城市之后至少 1 天后到达，可知 5 号城市可以在第 10 天到达。
对于 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。