Codeforces Round 154 (Div. 2) |
---|
Закончено |
Рассмотрим сетевой принтер, который функционирует следующим образом. Он начинает работать в момент времени 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 напечатано к концу 7-ой секунды, как и требовалось. А задания 2 и 3 напечатаны к концу 8-ой и 4-ой секунды соответственно.
Название |
---|