103433: [Atcoder]ABC343 D - Diversity of Scores

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

问题描述

高桥正在举办一场有N个编号为1到N的选手参加的比赛。 选手们将为了分数展开竞争。 目前，所有选手的分数都是0。

高桥的预见能力让他知道选手们的分数将如何变化。 具体来说，对于$i=1,2,\dots,T$，选手$A_i$的分数将在现在起的$i$秒后增加$B_i$分。 除此之外，分数不会再有任何其他变化。

喜欢分数多样性的小高想要知道在每个时刻选手们的分数中有多少种不同的分数值。 对于每个$i=1,2,\dots,T$，在现在起的$i+0.5$秒后选手们的分数中有多少种不同的分数值。

例如，如果在某个时刻选手们的分数分别为10分、20分、30分和20分，那么在那个时刻选手们的分数中有3种不同的分数值。

限制条件

• $1\leq N, T\leq 2\times 10^5$
• $1\leq A_i \leq N$
• $1\leq B_i \leq 10^9$
• 所有输入值都是整数。

输入

输入从标准输入中以以下格式给出：

$N$ $T$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_T$ $B_T$

输出

输出$T$行。 第$i$行 $(1\leq i \leq T)$ 应包含一个整数，表示在现在起的$i+0.5$秒后选手们的分数中有多少种不同的分数值。

样例输入1

3 4
1 10
3 20
2 10
2 10

样例输出1

2
3
2
2

让$S$表示选手1、2、3按此顺序的分数序列。 目前，$S=\lbrace 0,0,0\rbrace$。

• 1秒后，选手1的分数增加了10分，使得$S=\lbrace 10,0,0\rbrace$。 因此，在现在起的1.5秒后选手们的分数中有2种不同的分数值。
• 2秒后，选手3的分数增加了20分，使得$S=\lbrace 10,0,20\rbrace$。 因此，在现在起的2.5秒后选手们的分数中有3种不同的分数值。
• 3秒后，选手2的分数增加了10分，使得$S=\lbrace 10,10,20\rbrace$。 因此，在现在起的3.5秒后选手们的分数中有2种不同的分数值。
• 4秒后，选手2的分数增加了10分，使得$S=\lbrace 10,20,20\rbrace$。 因此，在现在起的4.5秒后选手们的分数中有2种不同的分数值。

样例输入2

1 3
1 3
1 4
1 3

样例输出2

1
1
1

样例输入3

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

样例输出3

2
2
3
3
4
4
5
5
6
5