分数的多样性

题目描述

高桥君正在举办一场有 $N$ 名选手（编号 $1$ 到 $N$）的比赛。 选手们将争夺分数。目前，所有选手的分数都是 $0$。

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

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

例如，如果在某一时刻选手们的分数为 $10$、$20$、$30$、$20$，则该时刻选手们的分数中有三种不同的分数值。

输入格式

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

N T
A_1 B_1
A_2 B_2
⋮
A_T B_T

输出格式

输出 $T$ 行。

第 $i$ 行 $(1 \le i \le T)$ 应输出一个整数，表示从现在起 $i+0.5$ 秒时，选手们的分数中不同分数值的数量。

样例

3 4
1 10
3 20
2 10
2 10

2
3
2
2

设 $S$ 为选手 $1, 2, 3$ 的分数按此顺序排列的序列。 目前，$S=\lbrace 0,0,0\rbrace$。

一秒后，选手 $1$ 的分数增加 $10$ 分，变为 $S=\lbrace 10,0,0\rbrace$。因此，从现在起 $1.5$ 秒时，选手们的分数中有两种不同的分数值。

两秒后，选手 $3$ 的分数增加 $20$ 分，变为 $S=\lbrace 10,0,20\rbrace$。因此，从现在起 $2.5$ 秒时，有三种不同的分数值。

三秒后，选手 $2$ 的分数增加 $10$ 分，变为 $S=\lbrace 10,10,20\rbrace$。因此，从现在起 $3.5$ 秒时，有两种不同的分数值。

四秒后，选手 $2$ 的分数增加 $10$ 分，变为 $S=\lbrace 10,20,20\rbrace$。因此，从现在起 $4.5$ 秒时，有两种不同的分数值。

1 3
1 3
1 4
1 3

1
1
1

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

2
2
3
3
4
4
5
5
6
5

数据范围

• $1 \le N, T \le 2 \times 10^5$
• $1 \le A_i \le N$
• $1 \le B_i \le 10^9$
• 所有输入值均为整数