关桑主持了一个比赛，有 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 秒后的时刻，选手得分中有多少个不同的得分值。

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