You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

关桑主持了一个比赛，有 $N$ 个编号为 $1$ 到 $N$ 的选手参加。这些选手将竞争得分。目前，所有选手的得分都是零。

关桑的预见能力让他知道选手得分将如何变化。具体来说，对于 $i=1,2,\dots,T$，从现在开始 $i$ 秒后，选手 $A_i$ 的得分将增加 $B_i$ 个点。在得分方面不会有其他变化。

关桑偏爱得分的多样性，他想知道每个时刻选手得分中会出现多少个不同的得分值。对于每个 $i=1,2,\dots,T$，找出在 $i+0.5$ 秒后的时刻，选手得分中有多少个不同的得分值。

例如，如果选手在某一时刻的得分分别为10、20、30和20，则在那一时刻，选手的得分中有三个不同的得分值。

输入格式

第一行两个整数 $N, T$ ，意义如题面描述。

接下来 $T$ 行，每行两个整数 $A_i, B_i$ ，表示在 $T$ 时刻选手 $A_i$ 的分数将增加 $B_i$ 个点。

输出格式

输出一共 $T$ 行。第 $i$ 行（$1≤i≤T$）应该包含一个整数，表示在 $i+0.5$ 秒后的时刻，选手得分中有多少个不同的得分值。

3 4
1 10
3 20
2 10
2 10

2
3
2
2

样例解释 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秒后的时刻，玩家得分中有两个不同的得分值。

数据范围与约定

• 对于 $40\%$ 的数据，$1 \leq B_i \leq 10^5$

• 对于 $100\%$ 的数据，$1≤N,T≤2×10^5, 1≤A_i≤N,1≤B_i≤10^9$ 所有输入值都是整数。