CF253E.Printer

Let's consider a network printer that functions like that. It starts working at time 0. In each second it can print one page of a text. At some moments of time the printer receives printing tasks. We know that a printer received n tasks. Let's number the tasks by consecutive integers from 1 to n. Then the task number i is characterised by three integers: t__i is the time when the task came, s__i is the task's volume (in pages) and p__i is the task's priority. The priorities of all tasks are distinct.

When the printer receives a task, the task goes to the queue and remains there until all pages from this task are printed. The printer chooses a page to print each time when it either stops printing some page or when it is free and receives a new task. Among all tasks that are in the queue at this moment, the printer chooses the task with the highest priority and next second prints an unprinted page from this task. You can assume that a task goes to the queue immediately, that's why if a task has just arrived by time t, the printer can already choose it for printing.

You are given full information about all tasks except for one: you don't know this task's priority. However, we know the time when the last page from this task was finished printing. Given this information, find the unknown priority value and determine the moments of time when the printer finished printing each task.

我们来考虑一台网络打印机，其工作方式如下：它从时间 0 开始工作，每秒可打印一页文本。在某些时刻，打印机接收到打印任务。已知打印机共接收了 $n$ 个任务。我们将这些任务按顺序编号为 $1$ 至 $n$。任务 $i$ 由三个整数刻画：$t_i$ 表示该任务到达的时间，$s_i$ 表示该任务的页数（即工作量），$p_i$ 表示该任务的优先级。所有任务的优先级互不相同。

当打印机接收到一个任务时，该任务立即进入队列，并一直保留在队列中，直至该任务的所有页面均被打印完毕。打印机每次在以下两种情形之一发生时选择下一页进行打印：（1）刚完成某一页的打印；或（2）当前空闲且恰好接收到一个新任务。在该时刻队列中的所有任务中，打印机总是选择优先级最高的那个任务，并于下一秒打印该任务中尚未打印的一页。可以假设任务一旦在时间 $t$ 到达即刻入队，因此若某任务恰于时间 $t$ 到达，则打印机在时间 $t$ 即可将其选中打印。

你已知全部 $n$ 个任务的完整信息，唯独其中一个任务的优先级未知。然而，我们已知该任务的最后一页完成打印的时间。基于这一信息，请确定该未知优先级的值，并求出打印机完成每个任务打印的具体时刻。

The first line contains integer n (1 ≤ n ≤ 50000). Next n lines describe the tasks. The i-th of these lines contains three integers t__i, s__i and p__i, separated by single spaces (0 ≤ t__i ≤ 109, 1 ≤ s__i, p__i ≤ 109). Exactly one task (let's assume that his number is x) has number -1 written instead of the priority. All priorities are different. The last line contains integer T — the time when the printer finished printing the last page of task x (1 ≤ T ≤ 1015). Numbers t__i are not necessarily distinct. The tasks in the input are written in the arbitrary order.

第一行包含一个整数 $n$（$1 \leq n \leq 50000$）。接下来的 $n$ 行描述了各项任务。其中第 $i$ 行包含三个整数 $t_i$、$s_i$ 和 $p_i$，以单个空格分隔（$0 \leq t_i \leq 10^9$，$1 \leq s_i, p_i \leq 10^9$）。恰好有一项任务（假设其编号为 $x$）的优先级位置写的是 $-1$ 而非具体优先级值。所有优先级互不相同。最后一行包含一个整数 $T$ —— 打印机完成打印任务 $x$ 的最后一页的时间（$1 \leq T \leq 10^{15}$）。数值 $t_i$ 不一定互异。输入中的任务以任意顺序给出。

In the first line print integer p__x — the priority of the task number x (1 ≤ p__x ≤ 109, remember that all priorities should be distinct). Then print n integers, the i-th of them represents the moment of time when the last page of the task number i finished printing.

It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.

第一行输出整数 $p_x$ —— 任务编号 $x$ 的优先级（$1 \le p_x \le 10^9$，注意所有优先级必须互不相同）。随后输出 $n$ 个整数，其中第 $i$ 个整数表示任务编号 $i$ 的最后一页完成打印的时刻。

保证至少存在一个解。若存在多个解，输出任意一个即可。

Let's consider the first test case. Let's assume that the unknown priority equals 4, then the printer's actions for each second are as follows:

• the beginning of the 1-st second (time 0). The queue has task 2. The printer prints the first page of this task;
• the beginning of the 2-nd second (time 1). The queue has tasks 2 and 3. The printer prints the first page of task 3;
• the beginning of the 3-rd second (time 2). The queue has tasks 2 and 3. The printer prints the second page of task 3;
• the beginning of the 4-th second (time 3). The queue has tasks 2 and 3. The printer prints the third (last) page of task 3. Thus, by the end of the 4-th second this task will have been printed;
• the beginning of the 5-th second (time 4). The queue has tasks 2 and 1. The printer prints the first page of task 1;
• the beginning of the 6-th second (time 5). The queue has tasks 2 and 1. The printer prints the second page of task 1;
• the beginning of the 7-th second (time 6). The queue has tasks 2 and 1. The printer prints the third (last) page of task 1. Thus, by the end of the 7-th second this task will have been printed;
• the beginning of the 8-th second (time 7). The queue has task 2. The printer prints the second (last) page of task 2. Thus, by the end of the 8-th second this task will have been printed.

In the end, task number 1 will have been printed by the end of the 7-th second, as was required. And tasks 2 and 3 are printed by the end of the of the 8-th and the 4-th second correspondingly.

我们来考虑第一个测试用例。假设未知的优先级为 $4$，则打印机在每一秒内的操作如下：

• 第 $1$ 秒初（时间 $0$）：队列中包含任务 $2$；打印机打印该任务的第一页；
• 第 $2$ 秒初（时间 $1$）：队列中包含任务 $2$ 和 $3$；打印机打印任务 $3$ 的第一页；
• 第 $3$ 秒初（时间 $2$）：队列中包含任务 $2$ 和 $3$；打印机打印任务 $3$ 的第二页；
• 第 $4$ 秒初（时间 $3$）：队列中包含任务 $2$ 和 $3$；打印机打印任务 $3$ 的第三页（即最后一页）。因此，到第 $4$ 秒末，该任务将被打印完毕；
• 第 $5$ 秒初（时间 $4$）：队列中包含任务 $2$ 和 $1$；打印机打印任务 $1$ 的第一页；
• 第 $6$ 秒初（时间 $5$）：队列中包含任务 $2$ 和 $1$；打印机打印任务 $1$ 的第二页；
• 第 $7$ 秒初（时间 $6$）：队列中包含任务 $2$ 和 $1$；打印机打印任务 $1$ 的第三页（即最后一页）。因此，到第 $7$ 秒末，该任务将被打印完毕；
• 第 $8$ 秒初（时间 $7$）：队列中仅剩任务 $2$；打印机打印任务 $2$ 的第二页（即最后一页）。因此，到第 $8$ 秒末，该任务将被打印完毕。

最终，任务 $1$ 将于第 $7$ 秒末完成打印，符合题目要求；而任务 $2$ 和 $3$ 则分别于第 $8$ 秒末和第 $4$ 秒末完成打印。