题目描述

皮皮假期吃了太多零食，导致体重大大大大大大大大增加。因此猴博士决定制定一个严格的进食计划，控制皮皮摄入的热量。

皮皮在连续 $M$ 分钟内只能进食 $N$ 次，每次进食的食物量都很少，进食时间可以忽略不计（皮皮：太少了吧）。对于第 $i$ 次进食，猴博士要求它不早于第 $S_i$ 分钟。

另外，猴博士还有 $C$ 条要求，每条要求都用一个三元组 $(a,b,t)$ 表示，表示第 $b$ 次进食至少要在第 $a$ 次进食至少 $t$ 分钟后进行。

因为猴博士的计划没有固定每次进食的具体时间，所以嘴馋的皮皮希望每次进食都越早越好。请你帮皮皮算出在满足所有条件的前提下，每次进食的最早时间。

因为进食计划经过猴博士的严格计算，所以一定存在至少一种合法的方案，使得每次进食的时间不晚于第 $M$ 分钟进行，并且所有的要求都能得到满足。

输入格式

第一行输入三个整数 $N,M,C$，分别表示进食次数、计划持续的分钟数和额外要求的数量。

第二行输入 $N$ 个整数 $S_1,S_2,\ldots,S_N$，其中 $1\le S_i\le M$，表示第 $i$ 次进食不能早于第 $S_i$ 分钟。

接下来 $C$ 行，每行输入三个整数 $a,b,t$，表示第 $b$ 次进食至少要在第 $a$ 次进食的 $t$ 分钟之后进行。保证 $a\ne b$。

输出格式

输出 $N$ 行。第 $i$ 行输出一个整数，表示在满足全部条件时，第 $i$ 次进食最早可以安排在第几分钟。

输入样例 #1

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

输出样例 #1

1
6
3
8

输入样例 #2

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

输出样例 #2

1
6
3
8

输入样例 #3

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

输出样例 #3

1
6
3
8

数据范围

对于 $30\%$ 的数据，$N,C\le 10^3$。

对于全部数据，$1\le N,C\le 10^5$，$2\le M\le 10^9$。