Codeforces Round 159 (Div. 2) |
---|
Закончено |
В m-этажном (m > 1) офисе международной корпорации CodeForces установили новейшую систему управления лифтом. Она работает следующим образом.
Все этажи офиса последовательно пронумерованы целыми числами от 1 до m. В момент времени t = 0 лифт находится на первом этаже, лифт пустой и никто не ждет лифта на других этажах. Далее, в моменты времени ti (ti > 0) к лифту подходят люди. Для простоты будем считать, что один человек пользуется лифтом только один раз в рассматриваемый промежуток времени. Для каждого человека известно 3 параметра: момент времени, в который человек подходит к лифту, этаж, на котором человек находится изначально, и этаж, на который он хочет попасть.
Передвижение лифта между этажами происходит следующим образом. В момент времени t (t ≥ 0, t — целое) лифт всегда находится на каком-то этаже. Лифт сначала выпускает всех людей, которые находятся в лифте и хотят попасть на текущий этаж. Затем он впускает всех людей, которые ждут лифта на текущем этаже. Если человек подходит к лифту ровно в момент времени t, то он успевает в него сесть. Можно считать, что все эти действия (посадка и высадка из лифта) совершаются мгновенно. После этого лифт решает, в каком направлении ему переместиться, и в момент времени (t + 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
В первом примере лифт действовал следующим образом:
Название |
---|