Description:


pyx喜欢出题给cyb做。为了增加难度,他有可能在cyb还没做完前面的题的时候就把新题目出给他。
假设pyx总共要给cyb出n道题,其中第i道题是在ti时刻出给cyb的,cyb需要花si秒才能AC此题。
pyx比较高产,出题时刻可能相同(也就是pyx可能同一时刻丢出了动态仙人掌和可持久化带插入仙人掌路径k大值给cyb)。
按照cyb的个人喜好,他给n道题目标上了互不相同的优先级pi。
cyb做题过程是这样的:
cyb收到题目是瞬间的事情。
每次,cyb先收到所有pyx新出的题。
接着,cyb把现在所有待解决的题目按照优先级瞬间排序。(当然优先级是互不相同的)
然后,cyb会花恰好1秒钟时间在那个优先级最高的题,然后解决该题需要花的时间减少1秒。如此循环。
由于是神犇之间的交流,十分有记录的意义,需要载入史册,这个光荣的任务就交给修电脑的oier们了。
现在给你n道题的ti,si,pi。然而不幸的是,由于奇怪的原因,你一不小心把某一道题的优先级弄丢了。
你为了掩饰自己的错误,通过不断打听,得知了cyb在时刻T时AC了这道优先级未知的题目。(即第T秒末,第T秒结束的时刻)
你想试着推测出优先级,然而很显然,方案可能不止一种。你决定编造这个题目的优先级,使得cyb仍会在时刻T AC此题。
除此之外,你还要帮cyb算出所有题目被解决的时刻,以展示你是多么的负责。
也就是说,你要求出一个可行的优先级,并求出在这个优先级下,所有题目被解决掉的时刻。

Input:


第一行输入一个正整数n。
接下来n行描述一个题目,第i行有三个整数分别是ti,si,pi,含义如前所述。有且仅有一个题目(我们不妨称其为题目x)的px=−1,表示该题的优先级未知。
最后一行包含一个整数T——任务x完成的时刻。
所有题目的优先级互不相同,但 ti 并不一定互不相同。

Output:


在第一行输出一个正整数px——即题目x的优先级(请记住所有题目的优先级必须互不相同)。接下来输出n个数字,第i个数字表示第ii个题目结束时的时间。
我们保证数据有解。如果有多解,输出任意一组解即可。
输出的优先级必须在[1,109+1]之内。

Sample Input:


Sample Output:


题解:


这个题目其实并不难,但一路做过来好崎岖的(´(ェ)`)
AC以后看题解,我开始怀疑我是不是水过去的。。。VFK的题解

直接按照题意进行模拟,先按照时间排序,把未知优先级前的处理完。
则在该题进入优先队列一直到T的这段时间内,完成了该题,并且完成了比它优先级高的题。
根据时间差,推出哪一些题目优先级比它要高,然后再枚举一下就可以了。

首次提交又被数据范围坑到了。。。没有开long long。。。所以我全部替换成了long long。。。
然后又发现用queue忘记判是否为空。。。
最后终于改过去了。
原谅我这题代码的放荡不羁( ̄▽ ̄)"