На далёкой планете устроили необычную гонку. Организаторы нарисовали круговую трассу, разделённую на $$$n$$$ позиций, которые пронумерованы по часовой стрелке от $$$1$$$ до $$$n$$$. На старте гонки в каждой из $$$n$$$ позиций находится ровно один бегун. Каждый бегун стремится завершить гонку, пробежав все позиции круга хотя бы один раз.

С одной позиции на соседнюю с ней бегуны пробегают за 1 единицу времени. Бегуны начинают бежать по часовой стрелке. Однако не всё так просто: в некоторые моменты времени на позициях появляются препятствия. Если бегун в этот момент времени оказался на позиции с препятствием, то он меняет направление движения на противоположное (начинает бежать в другую сторону). Если несколько бегунов оказались в позиции с препятствием, то они все меняют своё направление движения. Препятствие стоит ровно 1 единицу времени, то есть в следующий момент времени его уже нет. Также во время столкновения данная позиция для спортсмена считается посещённой.

Организаторы решили, что будет $$$m$$$ препятствий, $$$i$$$-е из которых появляется в момент времени $$$t_i$$$ на позиции $$$x_i$$$. Сама гонка начинается в момент времени $$$t = 0$$$. Помогите организаторам понять, через сколько секунд после начала забега каждый из спортсменов пробежит марафон, то есть посетит каждую позицию хотя бы по 1 разу.

Позиция, с которой начинает спортсмен, считается посещённой с самого начала.