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