E. Принтер
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

Рассмотрим сетевой принтер, который функционирует следующим образом. Он начинает работать в момент времени 0. Каждую секунду он может напечатать одну страницу текста. В некоторые моменты времени на принтер поступают задания на печать. Известно, что на принтер поступило n заданий. Пронумеруем задания последовательными целыми числами от 1 до n. Тогда задание с номером i характеризуется тремя целыми числами: ti — временем поступления задания, si — объемом задания (в страницах) и pi — приоритетом задания. Приоритеты всех заданий различны.

В тот момент, когда задание поступает на принтер, оно попадает в очередь и находится там до тех пор, пока все страницы из этого задания не будут напечатаны. Принтер выбирает страницу для печати каждый раз, когда заканчивает печатать какую-то страницу, либо в те моменты, когда поступает новое задание, а принтер был свободен. Среди всех заданий, имеющихся в очереди в данный момент, принтер выбирает задание с наибольшим приоритетом и в следующую секунду печатает очередную еще не напечатанную страницу из этого задания. Считайте, что задание попадает в очередь мгновенно, поэтому если в некоторый момент времени t задание только что поступило, то принтер уже может выбирать его для печати.

Вам дана полная информация о всех заданиях, кроме одного: для него неизвестен приоритет. Однако же известно, в какое время была завершена печать последней страницы из этого задания. По этой информации найдите неизвестное значение приоритета, а также определите времена окончания печати каждого из заданий.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 50000). Следующие n строк описывают задания. В i-й из этих строк записаны три целых числа ti, si и pi, разделенные одиночными пробелами (0 ≤ ti ≤ 109, 1 ≤ si, pi ≤ 109). Ровно для одного из заданий (пусть его номер x) вместо приоритета записано число -1. Все приоритеты различны. В последней строке записано целое число T — время завершения печати последней страницы задания с номером x (1 ≤ T ≤ 1015). Числа ti не обязательно различны. Задания записаны во входных данных в произвольном порядке.

Выходные данные

В первой строке выведите целое число px — приоритет задания с номером x (1 ≤ px ≤ 109, помните, что все приоритеты должны быть различны). Далее выведите n целых чисел, в i-ое из которых обозначает время завершения печати последней страницы задания с номером i.

Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.

Примеры
Входные данные
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
Примечание

Рассмотрим первый тестовый пример. Пусть неизвестный приоритет равен 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-ой секунды соответственно.