题目描述

小高正在举办一场有 $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 \leq i \leq T)$ 应包含一个整数，表示在 $i+0.5$ 秒后选手们的分数中有多少种不同的值。

样例

3 4
1 10
3 20
2 10
2 10

2
3
2
2

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解释

让 $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$
所有输入值都是整数。

来源

• AtCoder ABC343D