Problem G
Galactic Collegiate Programming Contest

Picture by GuillaumePreat on Pixabay, cc0

This year there are $n$ teams in the contest. The teams are numbered $1,2,\dots ,n$, and your favorite team has number $1$.

Like today, the score of a team is a pair of integers $(a,b)$ where $a$ is the number of solved problems and $b$ is the total penalty of that team. When a team solves a problem there is some associated penalty (not necessarily calculated in the same way as in the NCPC – the precise details are not important in this problem). The total penalty of a team is the sum of the penalties for the solved problems of the team.

Consider two teams $t_1$ and $t_2$ whose scores are $(a_1,b_1)$ and $(a_2,b_2)$. The score of team $t_1$ is better than that of $t_2$ if either $a_1>a_2$, or if $a_1=a_2$ and $b_1<b_2$. The rank of a team is $k+1$ where $k$ is the number of teams whose score is better.

You would like to follow the performance of your favorite team. Unfortunately, the organizers of GCPC do not provide a scoreboard. Instead, they send a message immediately whenever a team solves a problem.

Input

The first line of input contains two integers $n$ and $m$, where $1\le n\le {10}^5$ is the number of teams, and $1\le m\le {10}^5$ is the number of events.

Then follow $m$ lines that describe the events. Each line contains two integers $t$ and $p$ ($1\le t\le n$ and $1\le p\le 1000$), meaning that team $t$ has solved a problem with penalty $p$. The events are ordered by the time when they happen.

Output

Output $m$ lines. On the $i$’th line, output the rank of your favorite team after the first $i$ events have happened.

3 4
2 7
3 5
1 6
1 9

2
3
2
1