Ticket Counter Simulation

A ticket counter has \(N\) service windows numbered from 1 to \(N\). At any moment, if there is at least one person in the queue of a window, the person at the front is being served. When a new person arrives, they join the queue of the window that currently has the fewest people. In case of a tie, they choose the window with the smallest number.

When a service event occurs, an integer \(w\) is provided. Ideally the service should occur at window \(w\). However, if window \(w\) is empty at that moment, then you must search cyclically (i.e. check window \(w+1, w+2, \ldots, N, 1, 2, \ldots, w-1\)) to find the first window that is non‐empty, and serve the person at the front of that queue. If all windows are empty, nothing happens. Once a person enters a queue, they cannot change windows, and the order in the queue is preserved.

Your task is to simulate these events and output the order in which people are served.

inputFormat

The input is given from stdin and has the following format:

N M
event_1
event_2
...
event_M

The first line contains two integers \(N\) and \(M\), where \(N\) is the number of service windows and \(M\) is the number of events. Each of the next \(M\) lines contains an event. An arrival event is denoted by a line starting with 1 followed by a positive integer representing the person's unique identifier. A service event is denoted by a line starting with 0 followed by a positive integer \(w\) indicating the designated window. Remember, if the designated window is empty at a service event, you must check subsequent windows in a circular manner to find the first non-empty queue.

outputFormat

Print the served person identifiers in the order they were served on a single line on stdout, separated by a single space. If no service event results in a person being served, output an empty line.

3 8
1 105
1 102
1 110
0 3
1 120
0 1
0 2
0 1

110 105 102 120