Задача №113759. Лифт
В современном многоэтажном офисе крупной компании установлен новый лифт. В компании работает n сотрудников. Для проверки эффективности системы управления лифтом требуется провести моделирование его работы в конце рабочего дня, когда все сотрудники должны покинуть здание и спуститься на первый этаж. В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i -й сотрудник подходит к лифту в секунду t i на этаже a i , чтобы спуститься на первый этаж.
На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван, либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе с ним лифт могут ожидать и другие сотрудники.
В каждый момент времени не более одного вызова является активным.
Изначально лифт свободен и находится на первом этаже. Когда поступает первый вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если несколько вызовов поступает одновременно, активным становится вызов от сотрудника с меньшим номером.
Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один этаж в секунду.
При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все люди выходят из лифта, а лифт ожидает следующего вызова. Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов, активируется вызов, который поступил раньше других. Если несколько вызовов поступило одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.
Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия (лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается решение, на какой вызов лифт должен отреагировать). Требуется написать программу, которая по описанию вызовов лифта для каждого сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.
Первая строка входных данных содержит целые числа n и m — количество людей, вызывающих лифт, и количество этажей в здании ( 1 ≤ n ≤ 10 5 , 2 ≤ m ≤ 10 9 ).
Следующие n строк описывают сотрудников, i -я из этих строк содержит два целых числа t i и a i — секунду, в которую i -й сотрудник подходит к лифту, и номер этажа, на котором это происходит ( 1 ≤ t 1 ≤ t 2 ≤ … ≤ t n ≤ 10 9 , 2 ≤ a i ≤ m )
Выходные данные должны содержать n целых чисел, для каждого сотрудника требуется вывести секунду, в которую он выйдет из лифта на первом этаже.
Пример работы лифта по шагам показан в следующей таблице.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
5 4 2 3 2 4 5 2 5 3 9 3
6 12 6 12 12