YXZ正在举办一个比赛，有N  名选手参赛，编号从  1 到 N 。 这些选手将争夺积分。起初，所有选手的积分都是零。

YXZ具有预知能力，他知道选手的得分将如何变化。具体来说，对于i=1,2,…,T，在i 秒后，选手Ai 的得分将增加Bi分。得分不会有其他变化。

YXZ喜欢积分的多样性，他想知道每个时刻选手的积分中会出现多少不同的值。对于每个i=1,2,…,T,找出在i+0.5秒后选手的积分中有多少不同的值。

• 1 ≤ N,T ≤ 2×10⁵
• 1 ≤ Ai ≤ N
• 1 ≤ Bi ≤ 10⁹
• 所有输入值均为整数。

设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秒后，选手的积分中有两个不同的值。