灰灰的规律♂

灰灰的规律♂

题目描述

题目背景

上个题P1011 灰灰的液体♂中,灰灰 莫名其妙 在晚上把床单弄湿了。从那以后他一直有意留心在这件事上。

题目内容

灰灰在过去的\(N\)天里又发生了\(M\)次这件事,因为次数实在是太多, 他已经麻了 他有点记不住了
对于第\(i\)次xx,灰灰记得它不早于第\(S_i\)天发生。另外,他还记得\(C\)条信息,每条信息都是以下格式:

第 \(b\) 次xx在第 \(a\) 次xx结束至少 \(x\) 天后进行。

现在请你帮屑灰灰算出在满足所有条件的前提下,每次xx的最早日期。
保证灰灰的记忆没有错误,这意味着一定存在一种合法的方案,使得:

  • 第\(i\)次xx不早于第\(S_i\)天进行,且不晚于第\(M\)天进行;
  • 所有的记忆都得到满足;

输入输出格式

输入格式

第一行三个整数 \(N,M,C\)。保证 \(1 \leq N,C \leq 10^5\),\(2 \leq M \leq 10^9\)。
接下来一行包含 \(N\) 个整数 \(S_1, S_2 , \ldots, S_n\),保证 \(\forall 1 \leq i \leq n\),都满足 \(1 \leq S_i \leq M\)。
下面 \(C\) 行每行三个整数 \(a,b,x\),描述一条记忆。保证 \(a \neq b\),且 \(1 \leq x \leq M\)。

输出格式

输出 \(N\) 行,每行一个整数,第 \(i\) 行的数表示第 \(i\) 次xx的最早日期。

样例

输入

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

输出

1
6
3
8

来源

洛谷 P6145 [USACO20FEB] Timeline G

信息

ID
1012
难度
5
分类
拓扑排序差分约束 点击显示
标签
递交数
2
已通过
1
通过率
50%
上传者

相关

在下列训练计划中:

灰灰的通天塔 | Huihui‘s Babel