Elevator Simulation

A company has a building with \(m\) floors, numbered from 1 (bottom) to \(m\) (top). There are \(n\) employees working in the building, numbered 1 through \(n\). At the end of the day, every employee must take the elevator to floor 1. Initially, employee \(i\) is at floor \(a_i\) and arrives at the elevator lobby on that floor at time \(t_i\) seconds.

When an employee arrives at a floor, if someone has already pressed the elevator button on that floor, they just wait. Otherwise, they press the button, which sends a request signal. At any floor, there is at most one active request (the first person to press the button on that floor sets the pending request, and all subsequent arrivals on the same floor just join the waiting list).

The elevator begins idle at floor 1. It moves one floor per second (either upward or downward). As soon as the first request is made (or if the elevator is idle and there is a pending request), the elevator responds to a request. If multiple requests occur at the same moment, the one from the employee with the smallest number is served. The elevator then proceeds as follows:

• Upward phase: Starting at floor 1, the elevator travels upward to the floor \(F\) corresponding to the chosen request. It takes \(F-1\) seconds to reach floor \(F\). While the elevator is moving, new requests may be generated but they are not picked up during the upward travel.
• When the elevator arrives at floor \(F\) (at time \(T_{up}\)), all employees waiting on floor \(F\) board the elevator. (Note that employees who arrive exactly at that moment press the button first and then board.)
• Downward phase: The elevator then descends from floor \(F\) to floor 1. It moves one floor per second. On the way down, if the elevator arrives at a floor that has a pending request (i.e. someone pressed the button earlier or at that moment), it stops and picks up all waiting employees on that floor.

All employees who board during a trip ride until the elevator reaches floor 1 and then leave. The process continues (with the elevator starting afresh from floor 1) until all \(n\) employees have reached floor 1. Your task is to compute the time at which each employee reaches floor 1.

inputFormat

The first line contains two integers \(m\) and \(n\) \((2 \le m,\ n \le \) [limits]), representing the number of floors and the number of employees respectively.

Then \(n\) lines follow. The \(i\)-th of these lines contains two integers \(a_i\) and \(t_i\) \((1 \le a_i \le m,\ t_i \ge 0)\), denoting that employee \(i\) is initially at floor \(a_i\) and arrives at the elevator lobby at time \(t_i\) seconds.

You may assume that if multiple employees arrive at the same second on the same floor, the employee with the smaller index presses the button if none had pressed it before.

outputFormat

Output \(n\) lines. The \(i\)-th line should contain a single integer, the time (in seconds) at which employee \(i\) reaches floor 1.

sample

5 3
3 1
4 2
2 2

5
11
5