Galactic Collegiate Programming Contest

Time limit5sMemory limit512 MB

Summary

After each of m solve events, report the rank of team 1 among n teams ranked by solve count and then penalty.

Level: Medium6 of 10
Topics: Sorting, Binary search, Array, Implementation
Solved: No attempts yet

Problem

In 2117 the International Collegiate Programming Contest has grown a lot and it is now the Galactic Collegiate Programming Contest (GCPC).

This year $n$ teams take part. The teams are numbered $1, 2, \ldots, n$ , and your favorite team is team $1$ .

The score of a team is a pair of integers $(a, b)$ , where $a$ is the number of problems the team has solved and $b$ is its total penalty. Every solved problem carries a penalty, and the total penalty of a team is the sum of the penalties of the problems that team has solved. How a single penalty is computed does not matter in this problem.

Take two teams $t_1$ and $t_2$ with scores $(a_1, b_1)$ and $(a_2, b_2)$ . The score of $t_1$ is better than the score of $t_2$ if $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 with a better score.

The organizers publish no scoreboard. They only send a message the moment some team solves a problem. Report the rank of team $1$ after every message.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 10^5$ , $1 \le m \le 10^5$ ), the number of teams and the number of events.

Each of the next $m$ lines contains two integers $t$ and $p$ ( $1 \le t \le n$ , $1 \le p \le 1000$ ), meaning that team $t$ has solved a problem with penalty $p$ . The events are given in the order in which they happen.

Output

Print $m$ lines. On line $i$ , print the rank of team $1$ after the first $i$ events have happened.

Examples2

Example 1
Input
```
3 4
2 7
3 5
1 6
1 9
```
Expected output
```
2
3
2
1
```
Example 2
Input
```
3 5
1 10
2 9
3 11
2 1
1 1
```
Expected output
```
1
2
2
2
2
```