10. Лифт

Компания ElevatorCorp, в которой работает папа Васи, когда не ведет факультатив по математике, решила улучшить качество своих лифтов. Аналитическому отделу поручили выяснить, сколько времени проводит в движении лифт. В протоколе логирования все события вызова лифта имеют формат: timestamp start_floor destination_floor, где timestamp $-$ количество секунд от начала рассчитываемого периода, start_floor destination_floor $-$ этаж вызова лифта и этаж, на который едет пассажир.

Правила работы лифта аналитик Анна нашла в документации:

• в начальный момент времени (0) лифт стоит на первом этаже;

• если пассажир вызывает лифт, когда тот свободен, то лифт сразу же начинает двигаться к тому, кто его вызвал;

• если лифт едет с пассажиром и проезжает мимо другого пассажира, направление которого совпадает с направлением движения лифта, лифт остановится и заберет этого пассажира, после чего продолжит движение. Когда все люди выйдут на своих этажах, обработка событий продолжится в порядке поступления событий. Если событий в очереди нет, то лифт остается на этаже;

• если на этаже из лифта вышли все пассажиры, но здесь же ожидают другие пассажиры в направлении текущего движения, то они заходят в лифт, и он продолжает движение с сохранением направления;

• все люди соблюдают правила пользования лифтом, и если лифт едет вверх, а им необходимо вниз, они не зайдут в него;

• лифт может вместить любое количество людей;

• пассажиры входят и выходят мгновенно.

Добавим отдельно, пока пустой лифт едет к пассажиру, он не останавливается на промежуточных этажах. Если в какой-то момент времени одновременно происходит вызов на этаже, возле которого лифт стоит либо проезжает, то сначала обрабатывается действие человека, а затем в этот же момент $-$ текущее множество вызовов. Таким образом, в этот момент времени лифт может сразу открыться, если стоял на этаже, мгновенно остановиться и открыть двери, если направления движения лифта и пассажира совпадают, проехать мимо, если лифт движется пустым или направления движения пассажира и лифта не совпадают.

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

В первой строке содержатся числа $n$ и $t$ ($1 \le n \le 3\cdot10^5$, $1 \le t \le 1000$) $-$ количество пассажиров и время в секундах, за которое лифт перемещается между этажами.

Далее следует описание вызовов лифта. В $i$-й из следующих $n$ строк содержится по 3 числа $t_i$, $s_i$, $d_i$ ($1 \le t_i, s_i, d_i \le 10^9$, $s_i \ne d_i$) $-$ время вызова, стартовый этаж и этаж, на который едет человек, соответственно.

Гарантируется, что все $t_i$ различны и записаны в логе в порядке возрастания.

Для всех пассажиров в порядке их следования во входных данных выведите по одному числу в строке $-$ времени ожидания лифта на этаже в секундах.