AT_abc343_d.[ABC343D] Diversity of Scores

有 $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$，那么此时得分中有 $3$ 种不同的值。

输入按以下格式从标准输入读入。

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

输出 $T$ 行。对于每个 $i\ (1\leq i \leq T)$，第 $i$ 行输出在现在起第 $i+0.5$ 秒后选手们的得分中有多少种不同的值。

约束条件

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

样例解释 1

将选手 $1,2,3$ 的得分按顺序组成数列 $S$。初始时，$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$ 种不同的值。

由 ChatGPT 4.1 翻译