A. Лифт
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Вот и закончились многочисленные отборочные турниры на одно из самых престижных соревнований России Russian Codec Cup. Все n участников, прошедшие в финал соревнования, попали в огромный m-этажный 108- звездочный отель. Конечно же, первая мысль, приходящая в голову в таком месте: «А не покататься ли нам на лифте?».

Лифт в этом отеле перемещается между этажами всегда по одной и той же схеме. Изначально (в момент времени 0) лифт находится на этаже 1, далее он перемещается на этаж 2, потом на этаж 3, и так до этажа с номером m. После этого лифт перемещается на этаж m - 1, далее на этаж m - 2, и так до первого этажа. Этот процесс бесконечно повторяется. Известно, что лифт имеет бесконечную вместимость, а также что посадка пассажиров на любом этаже осуществляется мгновенно. Перемещение между этажами происходит за единицу времени.

Для каждого из n участников вам даны: si — на какой этаж приходит i-ый участник, fi — на какой этаж ему нужно попасть, ti — время, в которое i-ый участник приходит на этаж si.

Для каждого участника выведите минимальное время его прибытия на этаж fi.

Если участник приходит на этаж ровно в тот момент, когда приезжает лифт, считается, что участник успевает зайти в лифт. Если участник приходит на этаж si и на этот же этаж ему нужно попасть (si = fi), то время прибытия этого участника на этаж fi считается равным ti.

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

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

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

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

Выведите n строк по одному целому числу в каждой — для каждого участника время его прибытия на нужный этаж.

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

Рассмотрим первый пример. Первый участник приходит ко времени t = 3 на этаж s = 2. Чтобы добраться до этажа f = 4, ему придется подождать до момента времени 7, когда лифт во второй раз будет ехать наверх, сесть в лифт и проехать два этажа. В таком случае первый участник доберется до этажа f в момент времени 9. Второй участник приходит ко времени t = 0 на этаж s = 1, сразу же садится в лифт, и приезжает на этаж f = 2. Третий участник не ждет лифта, так как ему надо попасть на тот же этаж, на котором он начинает.