Рассмотрим сетевой принтер, который функционирует следующим образом. Он начинает работать в момент времени 0. Каждую секунду он может напечатать одну страницу текста. В некоторые моменты времени на принтер поступают задания на печать. Известно, что на принтер поступило n заданий. Пронумеруем задания последовательными целыми числами от 1 до n. Тогда задание с номером i характеризуется тремя целыми числами: ti — временем поступления задания, si — объемом задания (в страницах) и pi — приоритетом задания. Приоритеты всех заданий различны.
В тот момент, когда задание поступает на принтер, оно попадает в очередь и находится там до тех пор, пока все страницы из этого задания не будут напечатаны. Принтер выбирает страницу для печати каждый раз, когда заканчивает печатать какую-то страницу, либо в те моменты, когда поступает новое задание, а принтер был свободен. Среди всех заданий, имеющихся в очереди в данный момент, принтер выбирает задание с наибольшим приоритетом и в следующую секунду печатает очередную еще не напечатанную страницу из этого задания. Считайте, что задание попадает в очередь мгновенно, поэтому если в некоторый момент времени t задание только что поступило, то принтер уже может выбирать его для печати.
Вам дана полная информация о всех заданиях, кроме одного: для него неизвестен приоритет. Однако же известно, в какое время была завершена печать последней страницы из этого задания. По этой информации найдите неизвестное значение приоритета, а также определите времена окончания печати каждого из заданий.
Выходные данные
В первой строке выведите целое число px — приоритет задания с номером x (1 ≤ px ≤ 109, помните, что все приоритеты должны быть различны). Далее выведите n целых чисел, в i-ое из которых обозначает время завершения печати последней страницы задания с номером i.
Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.
Примечание
Рассмотрим первый тестовый пример. Пусть неизвестный приоритет равен 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-ой секунды соответственно.