题目描述

小高正在举办一场有 $N$ 名选手参加的比赛。选手编号从 $1$ 到 $N$。选手们将争夺积分。目前，所有选手的积分都是零。

小高的预知能力让他知道选手们的分数将如何变化。

具体来说，对于 $i=1,2,\dots,T$，第 $A_i$ 号选手的分数将在 $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$

$\vdots$

$A_T$ $B_T$

输出格式

输出 $T$ 行。

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

输入输出样例 #1

输入 #1

3 4
1 10
3 20
2 10
2 10

输出 #1

2
3
2
2

输入输出样例 #2

输入 #2

1 3
1 3
1 4
1 3

输出 #2

1
1
1

输入输出样例 #3

输入 #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

说明/提示

样例 1 解释

让 $S$ 表示选手 $1、2、3$ 的分数序列。目前，$S=\{0,0,0\}$。

• 一秒后，选手 $1$ 的分数增加 $10$ 分，使得 $S=\{10,0,0\}$。因此，在 $1.5$ 秒后选手们的分数中有两种不同的值。
• 两秒后，选手 $3$ 的分数增加 $20$ 分，使得 $S=\{10,0,20\}$。因此，在 $2.5$ 秒后选手们的分数中有三种不同的值。
• 三秒后，选手 $2$ 的分数增加 $10$ 分，使得 $S=\{10,10,20\}$。因此，在 $3.5$ 秒后选手们的分数中有两种不同的值。
• 四秒后，选手 $2$ 的分数增加 $10$ 分，使得 $S=\{10,20,20\}$。因此，在 $4.5$ 秒后选手们的分数中有两种不同的值。

数据范围

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