#1958. 挤奶

挤奶

题目描述

麦田老师 在过去的 MM 天内参加了 NN 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。

对于第 ii 次挤奶,麦田老师 记得它不早于第 SiS_i 天进行。另外,她还有 CC 条记忆,每条记忆形如一个三元组 (a,b,x)(a,b,x),含义是第 bb 次挤奶在第 aa 次挤奶结束至少 xx 天后进行。

现在请你帮 麦田老师 算出在满足所有条件的前提下,每次挤奶的最早日期。

保证 麦田老师 的记忆没有错误,这意味着一定存在一种合法的方案,使得:

  • ii 次挤奶不早于第 SiS_i 天进行,且不晚于第 MM 天进行;
  • 所有的记忆都得到满足;

输入格式

第一行三个整数 N,M,CN,M,C。保证 1N,C1051 \leq N,C \leq 10^52M1092 \leq M \leq 10^9

接下来一行包含 NN 个整数 S1,S2,,SnS_1, S_2 , \ldots, S_n,保证 1in\forall 1 \leq i \leq n,都满足 1SiM1 \leq S_i \leq M

下面 CC 行每行三个整数 a,b,xa,b,x,描述一条记忆。保证 aba \neq b,且 1xM1 \leq x \leq M

输出格式

输出 NN 行,每行一个整数,第 ii 行的数表示第 ii 次挤奶的最早日期。

样例 #1

样例输入 #1

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

样例输出 #1

1
6
3
8

提示

  • 测试点 242 \sim 4 满足 N,C103N,C \leq 10^3
  • 测试点 5105 \sim 10 没有特殊限制。