一百年后的 2117 年，国际大学生程序设计竞赛（NCPC 是其中的一部分）规模显著扩大，现在变成了银河大学生程序设计竞赛（GCPC）。

Picture by GuillaumePreat on Pixabay, cc0

今年共有 $n$ 支队伍参赛。队伍编号为 $1, 2, \dots, n$，你最喜欢的队伍编号为 1。

和今天一样，队伍的得分是一个整数对 $(a, b)$，其中 $a$ 是解出的题目数量，$b$ 是该队伍的总罚时。当队伍解出一道题目时，会产生一定的罚时（计算方式不一定与 NCPC 相同——具体细节在本题中并不重要）。队伍的总罚时是该队伍所有已解出题目的罚时之和。

考虑两支队伍 $t_1$ 和 $t_2$，其得分分别为 $(a_1, b_1)$ 和 $(a_2, b_2)$。如果满足 $a_1 > a_2$，或者 $a_1 = a_2$ 且 $b_1 < b_2$，则认为队伍 $t_1$ 的得分优于 $t_2$。队伍的排名为 $k + 1$，其中 $k$ 是得分优于该队伍的队伍数量。

你希望关注你最喜欢的队伍的表现。遗憾的是，GCPC 的组织者没有提供实时排行榜。相反，每当有队伍解出一道题目时，他们就会立即发送一条消息。

输入格式

第一行包含两个整数 $n$ 和 $m$，其中 $1 \le n \le 10^5$ 是队伍数量，$1 \le m \le 10^5$ 是事件数量。

接下来 $m$ 行描述这些事件。每行包含两个整数 $t$ 和 $p$（$1 \le t \le n$ 且 $1 \le p \le 1000$），表示队伍 $t$ 解出了一道罚时为 $p$ 的题目。事件按发生时间先后排序。

输出格式

输出 $m$ 行。第 $i$ 行输出在前 $i$ 个事件发生后，你最喜欢的队伍的排名。

样例

输入格式 1

3 4
2 7
3 5
1 6
1 9

输出格式 1

2
3
2
1