题目描述

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

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

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

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

输入格式

第一行一个字母 $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$ 表示这个任务 贺云艾 选择放弃这个任务。

样例

样例输入

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

样例输出

1 4 6 -1