Urinals in a restroom with of the Neues Messegebäude (prev. Schlachthofgelände), Dresden, 2003. Photo: Stefan Kühn, licensed under CC-BY SA 3.0

Many men’s rooms contain a linear array of wall-mounted fixtures for standing urination called urinals. According to an unwritten but consistently observed convention for using such a facility, the approaching gentleman seeks to occupy the position that maximizes distance from others, so as to discourage even unwitting visual acknowledgement. Concretely, this means selecting the midpoint of the longest continuous run of unoccupied fixtures. In the event of a tie, the urinal nearest the entrance is preferred, in order to minimise the number of other occupants one needs to pass. The system functions without discussion and generally prevents unnecessary proximity, preserving the polite fiction that no one is aware of anyone else.

If all urinals are occupied, arriving guests form an orderly line operating under the universally understood first-in-first-out principle. As urinals are vacated, the first guest in line gains access to the now-unoccupied fixtures. A urinal becomes available the very moment it is vacated.

Determine the urinals assigned by these rules to  guests in an initially empty men’s room of  urinals numbered from the entrance. For each guest you know his arrival time  and the duration  he needs to use the facility.

Input

The input consists of:

• One line with two integers and (, ), the number of guests and the number of urinals.
• lines, one for each guest. For , the th line contains two integers and (, ) the arrival time and duration of the th guest.

The lines are in ascending order of arrival time, and all arrival times are different.

Output

Output lines. For , output two integers: the index of the urinal used by the th guest, and the time when he starts using it.