Queue Jumpers

The Lunar New Year is approaching and people are lining up to buy railway tickets. In the darkness of the early morning, some impatient individuals decide to jump the queue. Initially, the queue is ordered with persons numbered from 1 to n. Then, m events occur. Each event is described by two integers x and p:

- Remove the person with id x from his current position in the queue.

- Reinsert the person at position p (1-indexed) of the current queue. All persons originally at position p and after are shifted one position to the right.

This operation is performed sequentially for all m events. Your task is to compute the final order of the queue after all of these operations.

Mathematically, if we denote the operation as removing the element and inserting it at a new position, the reinsertion can be thought of as:

\[ Q = \text{insert}_{p}(x, Q \setminus \{x\}) \]

where \(Q\) is the current queue.

inputFormat

The first line contains two integers, n and m.

• n (1 ≤ n ≤ 10⁵) is the number of persons.
• m (0 ≤ m ≤ 10⁵) is the number of queue-jump events.

Each of the next m lines contains two integers x and p:

• x is the id of the person who jumps the queue.
• p is the new position (1-indexed) where the person will be inserted.

It is guaranteed that every x corresponds to a person in the queue at the time of the event.

outputFormat

Output a single line containing the final order of persons in the queue. Output the person ids separated by a single space.

sample

5 2
3 1
5 3

3 1 5 2 4