AT_abc343_d [ABC343D] Diversity of Scores

[problemUrl]: https://atcoder.jp/contests/abc343/tasks/abc343_d 高橋君が主催するコンテストに、$ 1 $ から $ N $ までの番号が付けられた $ 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+0.5 $ 秒後の選手たちの得点には何種類の値が現れるかを整数として出力せよ。

### 制約 - $ 1\leq\ N,\ T\leq\ 2\times\ 10^5 $ - $ 1\leq\ A_i\ \leq\ N $ - $ 1\leq\ B_i\ \leq\ 10^9 $ - 入力は全て整数 ### Sample Explanation 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 $ 種類の値が現れます。