Problem B
OvalWatch

It’s the year 2020 and OvalWatch is the most popular massive online first person shooter game.

OvalWatch features a set of $N$ characters, and during a match, each player can choose one of these characters to play.

In order to keep each match interesting, for every match, OvalWatch requires that all players select unique characters and that all characters are selected (there are $N$ players in each match).

This requirement however is problematic because sometimes multiple players might want to play the same character. For example, suppose player $1$ wants to pick “TraySir”, and they tell everyone “I wanna be TraySir”, but player $2$ might have already picked “TraySir” and replies “I’m already TraySir”, leaving player $1$ disappointed and frustrated.

Player $1$ might then attempt to pick another character, say, “WindowMaker”, and they ask “What about WindowMaker?”. Unfortunately, another player may have picked WindowMaker in this time and replies “I’m already WindowMaker.”, leaving Player $1$ no choice but to pick yet someone else.

BeeLizard, the developer of OvalWatch, wants to eliminate the frustrating player experience of having to pick a character many times just to find one that’s available, and came up with an ingenious algorithm to do so.

Announcing BeeLizard’s OvalWatch’s newest feature: Ghost Leg.

In Ghost Leg, the players are are enumerated horizontally across the top of the page, while the in game characters are enumerated horizontally across the bottom of the page. Vertical lines are drawn connecting each person with the character directly below.

Next, “legs” are added to the page. Each leg is a horizontal line connecting two adjacent vertical lines, and must not touch any other leg.

Finally, each player $P$ traces a continuous path from themselves to a character at the bottom. If player $P$ encounters a leg while tracing the path, they must follow the leg across to the other vertical line, and resume tracing downwards. The character at the end of their path is the character assigned to player $P$.

As BeeLizard’s intern, you have to implement the GhostLeg feature of OvalWatch.

Input

The first line of the input contains $N$, the number of players, and $K$, the number of legs. It is guaranteed that $2\leq N\leq 5\, 000$ and $1\leq K\leq 100\, 000$.

The next $K$ lines of the input contains two integers $A_ i, B_ i$ describing each leg. $A_ i$ denotes the index of vertical line on the left side of the leg. Note that vertical lines are indexed from left to right starting from $0$. $B_ i$ denotes the distance between the top of the board and the leg’s position at the left vertical line. It is guaranteed that $0\leq A_ i<N-1$ and $1\leq B_ i\leq 10^9$.

Output

A single line containing $N$ integers, where the $i^\textrm {th}$ integer $V_ i$ denotes that character $V_ i$ is assigned to player $i$.

3 4
0 1
1 3
0 5
1 10

1 2 0

4 1
1 2

0 2 1 3