pyx喜欢出题给cyb做。为了增加难度，他有可能在cyb还没做完前面的题的时候就把新题目出给他。

假设pyx总共要给cyb出$n$道题，其中第$i$道题是在$t_i$时刻出给cyb的，cyb需要花$s_i$秒才能AC此题。

pyx比较高产，出题时刻可能相同（也就是pyx可能同一时刻丢出了动态仙人掌和可持久化带插入仙人掌路径k大值给cyb）。

按照cyb的个人喜好，他给$n$道题目标上了互不相同的优先级$p_i$。

cyb做题过程是这样的：

• cyb收到题目是瞬间的事情。
• 每次，cyb先收到所有pyx新出的题。
• 接着，cyb把现在所有待解决的题目按照优先级瞬间排序。（当然优先级是互不相同的）
• 然后，cyb会花恰好$1$秒钟时间在那个优先级最高的题，然后解决该题需要花的时间减少$1$秒。如此循环。

由于是神犇之间的交流，十分有记录的意义，需要载入史册，这个光荣的任务就交给修电脑的oier们了。

现在给你$n$道题的$t_i,s_i,p_i$。然而不幸的是，由于奇怪的原因，你一不小心把某一道题的优先级弄丢了。

你为了掩饰自己的错误，通过不断打听，得知了cyb在时刻$T$时AC了这道优先级未知的题目。（即第$T$秒末，第$T$秒结束的时刻）

你想试着推测出优先级，然而很显然，方案可能不止一种。你决定编造这个题目的优先级，使得cyb仍会在时刻$T$ AC此题。

除此之外，你还要帮cyb算出所有题目被解决的时刻，以展示你是多么的负责。

也就是说，你要求出一个可行的优先级，并求出在这个优先级下，所有题目被解决掉的时刻。

输入格式

第一行输入一个正整数$n$。

接下来$n$行描述一个题目，第$i$行有三个整数分别是$t_i,s_i,p_i$，含义如前所述。有且仅有一个题目（我们不妨称其为题目$x$）的$p_x=-1$，表示该题的优先级未知。

最后一行包含一个整数$T$——任务$x$完成的时刻。

所有题目的优先级互不相同，但 $t_i$ 并不一定互不相同。

输出格式

在第一行输出一个正整数$p_x$——即题目$x$的优先级（请记住所有题目的优先级必须互不相同）。接下来输出$n$个数字，第$i$个数字表示第$i$个题目结束时的时间。

我们保证数据有解。如果有多解，输出任意一组解即可。

输出的优先级必须在$[1,{10}^9+1]$之内。

样例一

input

3
4 3 -1
0 2 2
1 3 3
7

output

4
7 8 4

样例二

input

3
3 1 2
2 3 3
3 1 -1
4

output

4
7 6 4

样例三

见样例数据下载

限制与约定

保证$0\le t_i\le {10}^9,1\le s_i,p_i\le {10}^9,1\le T\le {10}^{15}$。（$p_x$例外，$p_x=-1$）

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载