Нархан недавно создал свою оригинальную игру-платформер. Как в большинстве игр похожего жанра, всё действие игры происходит в двумерном пространстве. Весь мир игры можно описать как один большой прямоугольник, соединяющий точки и . Все объекты в игре

Нархан недавно создал свою оригинальную игру-платформер. Как в большинстве игр похожего жанра, всё действие игры происходит в двумерном пространстве. Весь мир игры можно описать как один большой прямоугольник, соединяющий точки $(0,0)$ и $\left(m, 10^{9}\right)$. Все объекты в игре находятся внутри этого прямоугольника. Прямая $y=0$ считается землей. В игре действует обычная гравитация. Игрок начинает игру в точке $(0,0)$ и для победы нужно добраться до точки ( $m, 0$ ). В игре также присутствуют $n$ препятствий. Каждое препятствие также можно описать как прямоугольник. Все препятствия лежат на земле, т.е. напрямую касаются земли. Расположение каждого из них описывается тремя целыми числами $L_{i}, R_{i}$ и $H_{i}-x$-координатой левого конца прямоугольника, $x$-координатой правого конца прямоугольника и высотой прямоугольника. Препятствия не пересекаются между собой, но могут касаться друг-друга. Также гарантируется, что никакое препятствие не содержит начальную точку $(0,0)$ и конечную точку $(m, 0)$. Игрок может свободно перемещаться налево или направо. Однако игрок не может проходить сквозь препятствия или обходить их. Но игрок может подниматься и опускаться по сторонам препятствий. На каждое перемещение игрока тратится ровно одна секунда. Нархан попросил Аманбола пройти эту игру. Аманбол очень ленивый, поэтому он не хочет тратить большое количество времени на прохождение игры. Поэтому перед началом игры он может попросить Нархана передвинуть некоторые препятствия. Он может выбрать произвольное препятствие $i(1<=i<=n)$ и попросить Нархана подвинуть это препятствие на одну единицу налево или на одну единицу направо при условии что все правила игры всё еще выполняются (препятствия не должны пересекаться и не должны содержать начальную или конечную точку). Нархану потребуется ровно $C_{i}$ секунд чтобы выполнить просьбу