#9029. 「洛谷P6145」Timeline G 普及+/提高

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

Bessie 在过去的 天内参加了 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。

对于第 次挤奶,Bessie 记得它不早于第 天进行。另外,她还有 条记忆,每条记忆形如一个三元组 ,含义是第 次挤奶在第 次挤奶结束至少 天后进行。

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

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

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

输入格式

第一行三个整数 。保证

接下来一行包含 个整数 ,保证 ,都满足

下面 行每行三个整数 ,描述一条记忆。保证 ,且

输出格式

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

样例

样例输入

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

样例输出

1
6
3
8

数据范围与提示

  • 测试点 满足
  • 测试点 没有特殊限制。