Score: $400$ points

问题描述

Takahashi 正在举办一场有 $N$ 名选手参加的比赛，选手编号为 $1$ 到 $N$。这些选手将通过获取积分进行竞争。目前，所有选手的积分都是零。

凭借 Takahashi 的预见能力，他能预知选手们的积分变化情况。具体来说，在 $i=1,2,\dots,T$ 时，编号为 $A_i$ 的选手将在从现在开始的 $i$ 秒后，其积分将增加 $B_i$ 分。除此之外，积分不会发生其他变化。

偏好积分多样性变化的 Takahashi 想要知道在每一时刻选手们的积分中会出现多少种不同的积分值。对于每个 $i=1,2,\dots,T$，请找出从现在开始的 $i+0.5$ 秒时，选手们积分中的不同积分值的数量。

例如，若选手们在某个时刻的积分分别为 $10$、$20$、$30$ 和 $20$ 分，则此时选手们积分中有三个不同的积分值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi is hosting a contest with $N$ players numbered $1$ to $N$. The players will compete for points. Currently, all players have zero points.

Takahashi's foreseeing ability lets him know how the players' scores will change. Specifically, for $i=1,2,\dots,T$, the score of player $A_i$ will increase by $B_i$ points at $i$ seconds from now. There will be no other change in the scores.

Takahashi, who prefers diversity in scores, wants to know how many different score values will appear among the players' scores at each moment. For each $i=1,2,\dots,T$, find the number of different score values among the players' scores at $i+0.5$ seconds from now.

For example, if the players have $10$, $20$, $30$, and $20$ points at some moment, there are three different score values among the players' scores at that moment.

Constraints

• $1\leq N, T\leq 2\times 10^5$
• $1\leq A_i \leq N$
• $1\leq B_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $T$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_T$ $B_T$

Output

Print $T$ lines. The $i$-th line $(1\leq i \leq T)$ should contain an integer representing the number of different score values among the players' scores at $i+0.5$ seconds from now.

Sample Input 1

3 4
1 10
3 20
2 10
2 10

Sample Output 1

2
3
2
2

Let $S$ be the sequence of scores of players $1, 2, 3$ in this order. Currently, $S=\lbrace 0,0,0\rbrace$.

• After one second, the score of player $1$ increases by $10$ points, making $S=\lbrace 10,0,0\rbrace$. Thus, there are two different score values among the players' scores at $1.5$ seconds from now.
• After two seconds, the score of player $3$ increases by $20$ points, making $S=\lbrace 10,0,20\rbrace$. Thus, there are three different score values among the players' scores at $2.5$ seconds from now.
• After three seconds, the score of player $2$ increases by $10$ points, making $S=\lbrace 10,10,20\rbrace$. Therefore, there are two different score values among the players' scores at $3.5$ seconds from now.
• After four seconds, the score of player $2$ increases by $10$ points, making $S=\lbrace 10,20,20\rbrace$. Therefore, there are two different score values among the players' scores at $4.5$ seconds from now.

Sample Input 2

1 3
1 3
1 4
1 3

Sample Output 2

1
1
1

Sample Input 3

10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225

Sample Output 3

2
2
3
3
4
4
5
5
6
5

update @ 2024/3/10 01:16:11