OpenKattis
Take Home Assignment 3B (You have to implement your own AVL Tree to solve this: TAs will check submissions): 15 September 8:00am - 29 October 9:30am

#### Start

2019-10-15 00:00 UTC

## Take Home Assignment 3B (You have to implement your own AVL Tree to solve this: TAs will check submissions): 15 September 8:00am - 29 October 9:30am

#### End

2019-10-30 01:30 UTC
The end is near!
Session is over.
Not yet started.
Session is starting in -55 days 16:12:57

361:30:00

0:00:00

# Problem AGalactic Collegiate Programming Contest

Picture by GuillaumePreat on Pixabay, cc0
One hundred years from now, in $2117$, the International Collegiate Programming Contest (of which the NCPC is a part) has expanded significantly and it is now the Galactic Collegiate Programming Contest (GCPC).

This year there are $n$ teams in the contest. The teams are numbered $1,2,\ldots ,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.

Sample Input 1 Sample Output 1
3 4
2 7
3 5
1 6
1 9

2
3
2
1