E. Жадный Лифт
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В m-этажном (m > 1) офисе международной корпорации CodeForces установили новейшую систему управления лифтом. Она работает следующим образом.

Все этажи офиса последовательно пронумерованы целыми числами от 1 до m. В момент времени t = 0 лифт находится на первом этаже, лифт пустой и никто не ждет лифта на других этажах. Далее, в моменты времени ti (ti > 0) к лифту подходят люди. Для простоты будем считать, что один человек пользуется лифтом только один раз в рассматриваемый промежуток времени. Для каждого человека известно 3 параметра: момент времени, в который человек подходит к лифту, этаж, на котором человек находится изначально, и этаж, на который он хочет попасть.

Передвижение лифта между этажами происходит следующим образом. В момент времени t (t ≥ 0, t — целое) лифт всегда находится на каком-то этаже. Лифт сначала выпускает всех людей, которые находятся в лифте и хотят попасть на текущий этаж. Затем он впускает всех людей, которые ждут лифта на текущем этаже. Если человек подходит к лифту ровно в момент времени t, то он успевает в него сесть. Можно считать, что все эти действия (посадка и высадка из лифта) совершаются мгновенно. После этого лифт решает, в каком направлении ему переместиться, и в момент времени (t + 1) лифт попадает на выбранный этаж.

Лифт выбирает направление движения по следующему алгоритму.

  • Если лифт пустой, и в текущий момент времени ни на одном этаже никто его не ждет, то лифт остается на текущем этаже.
  • Иначе, пусть лифт находится на этаже номер x (1 ≤ x ≤ m). Тогда лифт вычисляет «приоритеты» направлений pup и pdown: pup — это сумма количества людей, которые ждут лифт на этажах с номерами больше x, и количества людей в лифте, которые хотят попасть на этаж с номером больше x; pdown — это сумма количества людей, которые ждут лифт на этажах с номерами меньше x, и количества людей в лифте, которые хотят попасть на этаж с номером меньше x. Если pup ≥ pdown, то лифт поднимается на один этаж выше текущего (то есть с этажа x на этаж x + 1), иначе лифт опускается на один этаж ниже текущего (то есть с этажа x на этаж x - 1).

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

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

В первой строке заданы два целых числа, разделенных пробелом: n, m (1 ≤ n ≤ 105, 2 ≤ m ≤ 105) — количество людей и этажей в здании соответственно.

В следующих n строках содержатся по три целых числа, разделенных пробелами: ti, si, fi (1 ≤ ti ≤ 109, 1 ≤ si, fi ≤ m, si ≠ fi) — момент времени, когда i-тый человек начнет ждать лифта, номер этажа, на котором изначально находится i-тый человек, и номер этажа, на который он хочет попасть.

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

Выведите n строк. В i-той строке выведите единственное целое число — момент времени, в который i-тый человек попадет на нужный ему этаж. Люди пронумерованы в том порядке, в котором они заданы во входных данных.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3 10
1 2 7
3 6 5
3 4 8
Выходные данные
7
11
8
Входные данные
2 10
1 2 5
7 4 5
Выходные данные
5
9
Примечание

В первом примере лифт действовал следующим образом:

  • t = 1. Лифт находится на этаже номер 1. Лифт пуст. На этаже номер 2 ждет один человек. pup = 1 + 0 = 1, pdown = 0 + 0 = 0, pup ≥ pdown. Значит, лифт перемещается на этаж номер 2.
  • t = 2. Лифт находится на этаже номер 2. В лифт заходит один человек, который хочет попасть на этаж номер 7. pup = 0 + 1 = 1, pdown = 0 + 0 = 0, pup ≥ pdown. Значит, лифт перемещается на этаж номер 3.
  • t = 3. Лифт находится на этаже номер 3. В лифте находится один человек, который хочет попасть на этаж номер 7. На этажах с номерами 4 и 6 лифт ждут два человека. pup = 2 + 1 = 3, pdown = 0 + 0 = 0, pup ≥ pdown. Значит, лифт перемещается на этаж номер 4.
  • t = 4. Лифт находится на этаже номер 4. В лифте находится один человек, который хочет попасть на этаж номер 7. В лифт заходит один человек, который хочет попасть на этаж номер 8. На этаже с номером 6 лифт ждет один человек. pup = 1 + 2 = 3, pdown = 0 + 0 = 0, pup ≥ pdown. Значит, лифт перемещается на этаж номер 5.
  • t = 5. Лифт находится на этаже номер 5. В лифте находятся два человека, которые хотят попасть на этажи с номерами 7 и 8 соответственно. На этаже с номером 6 лифт ждет один человек. pup = 1 + 2 = 3, pdown = 0 + 0 = 0, pup ≥ pdown. Значит, лифт перемещается на этаж номер 6.
  • t = 6. Лифт находится на этаже номер 6. В лифте находятся два человека, которые хотят попасть на этажи с номерами 7 и 8 соответственно. В лифт заходит один человек, который хочет попасть на этаж номер 5. pup = 0 + 2 = 2, pdown = 0 + 1 = 1, pup ≥ pdown. Значит, лифт перемещается на этаж номер 7.
  • t = 7. Лифт находится на этаже номер 7. Из лифта выходит человек, который хотел попасть на этаж номер 7. В лифте находятся два человека, которые хотят попасть на этажи с номерами 8 и 5 соответственно. pup = 0 + 1 = 1, pdown = 0 + 1 = 1, pup ≥ pdown. Значит, лифт перемещается на этаж номер 8.
  • t = 8. Лифт находится на этаже номер 8. Из лифта выходит человек, который хотел попасть на этаж номер 8. В лифте находится один человек, который хочет попасть на этаж номер 5. pup = 0 + 0 = 0, pdown = 0 + 1 = 1, pup < pdown. Значит, лифт перемещается на этаж номер 7.
  • t = 9. Лифт находится на этаже номер 7. В лифте находится один человек, который хочет попасть на этаж номер 5. pup = 0 + 0 = 0, pdown = 0 + 1 = 1, pup < pdown. Значит, лифт перемещается на этаж номер 6.
  • t = 10. Лифт находится на этаже номер 6. В лифте находится один человек, который хочет попасть на этаж номер 5. pup = 0 + 0 = 0, pdown = 0 + 1 = 1, pup < pdown. Значит, лифт перемещается на этаж номер 5.
  • t = 11. Лифт находится на этаже номер 5. Из лифта выходит человек, который хотел попасть на этаж номер 5. Лифт пуст и никто его не ждет, а значит, лифт остается на этаже номер 5.