seuOJ289 - 佛系大帝

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1500 ms
• 空间限制：256 MiB
• 题目标签：春季, 夏季, 校赛, 2020

题目描述

KGS 大帝有 $n$ 个条任务，然而 KGS 是一个很佛系的人，所以来不及做的事情就不做了(同学们不能学习ta)。

第 $i$ 条任务有三个属性 $a_i,t_i,b_i$ ,表示这一个任务 $a_i$ 时刻发布，需要做 $t_i$ 时间，如果在发布后的 $b_i$ 时间内没有开始做，KGS 就会选择放弃做这件事。

当一条任务做完之后 KGS 才会选择开始下一条任务，KGS 会选择剩余任务中发布时间最早的任务作为下一件任务（保证发布时间 $a_i$ 各不相同）。

对于每个任务请回答：KGS 会不会做这个任务呢？如果会做，又是什么时候开始做呢？

输入格式

第一行一个字母 $n$ 表示有 $n(0\leq n\leq 10^5)$ 个任务。

接下来 $n$ 行中 第 $i$ 行有三个字母 $a_i,t_i,b_i(1\leq a_i,t_i,b_i\leq10^9)$ 表示第 $i$ 号任务的三个属性。

输出格式

一行共 $n$ 个数字，第 $i$ 个数字表示第 $i$ 个任务什么时候开始被做，用 $-1$ 表示这个任务 KGS 选择放弃这个任务。

样例

样例输入

4
1 3 3
2 2 2 
4 3 2 
3 9 1

样例输出

1 4 6 -1