题目描述

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

婷婷在连续 $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

8 1000000000 28
38 72 291 856 260 992 218 859
4 8 2
2 4 21
1 5 10
2 7 71
5 6 93
1 6 97
3 4 71
3 4 22
5 7 76
7 8 98
7 8 43
2 5 98
6 8 55
6 7 66
1 7 58
4 6 49
3 7 69
2 4 35
1 8 1
4 6 97
5 6 9
1 7 66
3 7 71
1 5 81
2 8 92
2 8 40
1 8 15
5 7 16

输出样例 #2

38
72
291
856
260
992
1058
1156

输入样例 #3

14 1000000000 56
911 515 985 396 999 949 445 544 828 630 324 43 43 846
5 11 47
6 13 37
2 8 82
4 8 72
9 11 23
4 8 23
3 14 82
3 13 80
1 8 42
5 9 16
10 12 80
1 4 5
3 8 1
3 9 61
2 5 92
3 13 55
1 8 5
10 14 7
8 13 96
10 11 63
4 14 17
2 11 56
4 12 26
4 8 71
3 14 14
2 14 36
4 7 57
1 11 37
5 10 50
4 9 39
10 12 94
1 6 96
5 14 78
5 9 100
2 13 89
2 5 36
1 8 74
4 11 75
1 11 64
5 8 46
1 7 8
2 4 89
4 7 50
4 9 23
9 13 46
2 14 44
7 13 59
10 13 80
3 10 15
5 14 13
5 13 45
6 11 71
4 7 25
4 5 37
2 14 16
6 9 55

输出样例 #3

911
515
985
916
999
1007
973
1045
1099
1049
1122
1143
1145
1077

数据范围

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

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