#P10. 【UTR #1】pyx的难题

【UTR #1】pyx的难题

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]$之内

3
4 3 -1
0 2 2
1 3 3
7
4
7 8 4
3
3 1 2
2 3 3
3 1 -1
4
4
7 6 4

样例三

见样例数据下载

限制与约定

测试点编号 $n$的大小 $t$的大小
1$n \le 5$$t_i \le 5$
2$n \le 10$$t_i \le 10$
3$n \le 50$$t_i \le 50$
4~12$n \le 100$$t_i \le 10000$
13~14$n \le 50000$$t_i \le 50000$
15~18$n \le 50000$$t_i \le 1000000000$
19~20$n \le 300000$$t_i \le 1000000000$

保证$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\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载