当前没有测试数据。

题目描述

周周在玩游戏《明日方舟》的破解版《昨月圆车》。众所周知，在《昨月圆车》中，最强的干员是异客，他能降下强大的雷霆惩罚敌人。客门。

众所周知，人被雷劈就会死，《昨月圆车》有最真实的物理引擎，如果 A 被雷劈死了，那么他周围距离 $d$ 之内的人例如 B 也会被劈死，然后与 B 距离 $d$ 之内的人也会被劈死，以此类推，雷光的威严会不断传递下去……这些传递雷劈的死亡视为同时发生。

给定一张二维平面地图，地图中初始没有敌人。之后给出 $q$ 次询问，每次询问给出一个坐标 $(x_i,y_i)$ ，意为在地图上此坐标点处新增加一名敌人。特别的，所有敌人的 $x$ 坐标均不相同。

异客可以进行无限次攻击，两次攻击之间有一定时间间隔，每次攻击可以选择全图任意一名（活着的）敌人。敌人的死亡规则如第二段所示。

请输出每次询问之后，异客最少需要多少次攻击才能将地图上所有敌人全部杀死。

输入描述

第一行给出一个非负整数 $d (0 \leqslant d \leqslant 100)$，意为最短传递攻击的距离。

接下来一行给出一个非负整数 $q (1 \leqslant q \leqslant 10^5)$。

接下来 $q$ 行，每行给出两个整数 $x_i,y_i (1 \leqslant x_i, y_i \leqslant 10^9)$，意为在地图上坐标 $(x_i,y_i)$处新增加一名敌人。

输出描述

输出 $q$ 行，每行一个整数，代表每次询问之后，异客最少需要多少次攻击才能将地图上所有敌人全部杀死。输入

样例

1
4
1 1
3 1
2 1
10 10

1
2
1
2

提示

第一次询问之后，在坐标 $(1,1)$ 处新增了一名敌人，此时场上共 $1$ 名敌人，异客只需攻击 $1$ 次即可；

第二次询问之后，在坐标 $(3,1)$ 处新增了一名敌人，此时场上共 $2$ 名敌人，由于两名敌人的间隔距离大于 $d$ ，因此异客需要攻击 $2$ 次；

第三次询问之后，在坐标 $(2,1)$ 处新增了一名敌人，此时场上共 $3$ 名敌人，假设异客第一次劈雷的目标是坐标为 $(1,1)$ 的敌人，由于第3个敌人与被劈到的敌人距离小于 $1$，于是第3个敌人也被劈到了；而第2个敌人与第3个敌人距离也小于 $1$，因此第2个敌人也被劈到了。故而最终，异客只需要 $1$ 次攻击即可击杀所有敌人。

第四次询问同理。