15022번 - Galactic Collegiate Programming Contest 다국어

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, . . . , 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₁ and t₂ whose scores are (a₁, b₁) and (a₂, b₂). The score of team t₁ is better than that of t₂ if either a₁ > a₂, or if a₁ = a₂ and b₁ < b₂. 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.

The first line of input contains two integers n and m, where 1 ≤ n ≤ 10⁵ is the number of teams, and 1 ≤ m ≤ 10⁵ is the number of events.

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

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