题目内容

在二维平面上分布着 $N$ 个基站，每个基站 $P_i$ 的位置由其坐标 $(x_i, y_i)$ 表示。现在需要根据基站之间的空间邻近关系，将每个基站划分为核心点、边界点或噪声点。

给定距离门限 $\epsilon_{dist}$ 和数量门限 $MinPts$。任意两个基站 $P_i$ 与 $P_j$ 之间的空间距离定义为曼哈顿距离：

若 $d_{space}(P_i,P_j) \le \epsilon_{dist}$，则称 $P_j$ 位于 $P_i$ 的空间邻域内。需要注意，基站 $P_i$ 到自身的曼哈顿距离为 0，因此每个基站一定包含在自己的空间邻域中。

对于某个基站 $P$，将其空间邻域内所有基站的数量记为 $Count$，并按以下规则判定：

• 若 $Count \ge MinPts$，则 $P$ 被标记为核心点（$Core$）。
• 若 $Count < MinPts$，但 $P$ 的空间邻域内至少存在一个核心点，则 $P$ 被标记为边界点（$Border$）。
• 若 $P$ 既不是核心点，也不是边界点，则 $P$ 被标记为噪声点（$Noise$）。

最终需要输出每个基站的类别编号：0 表示核心点，1 表示边界点，2 表示噪声点。

约束条件：

• 基站数量 $N$ 在 1 到 2000 之间。
• 距离门限 $\epsilon_{dist}$ 在 0 到 10000 之间。
• 邻域数量门限 $MinPts$ 在 1 到 $N$ 之间。
• 每个坐标分量 $x$ 和 $y$ 都在 -10000 到 10000 之间。

输入描述

第一行包含三个整数，依次为 $N$、$\epsilon_{dist}$ 和 $MinPts$，用空格分隔。其中 $N$ 表示基站数量，$\epsilon_{dist}$ 表示距离门限，$MinPts$ 表示邻域数量门限。

接下来共 $N$ 行，每行包含两个整数 $x$ 和 $y$，表示一个基站的平面坐标。

输出描述

输出共 $N$ 行，每行一个整数。第 $i$ 行表示第 $i$ 个基站的分类结果：0 表示核心点，1 表示边界点，2 表示噪声点。

样例1

输入

5 1 3
0 0
1 0
2 0
10 10
3 0

输出

1
0
0
2
1

说明

距离门限 $\epsilon_{dist}$ 为 1，数量门限 $MinPts$ 为 3。共有 5 个基站，按输入顺序记为 $P_1$ 到 $P_5$。

对于 $P_2$，它与 $P_1$ 的距离为 $|1-0|+|0-0|=1$，与 $P_3$ 的距离为 $|1-2|+|0-0|=1$，加上自身后邻域数量为 3，达到 $MinPts$，因此 $P_2$ 是核心点。

对于 $P_3$，它与 $P_2$ 的距离为 $|2-1|+|0-0|=1$，与 $P_5$ 的距离为 $|2-3|+|0-0|=1$，加上自身后邻域数量为 3，因此 $P_3$ 也是核心点。

对于 $P_1$，邻域内包含自身和 $P_2$，数量为 2，小于 3，但邻域内存在核心点 $P_2$，因此 $P_1$ 是边界点。

对于 $P_5$，邻域内包含自身和 $P_3$，数量为 2，小于 3，但邻域内存在核心点 $P_3$，因此 $P_5$ 是边界点。

对于 $P_4$，邻域内只有自身，数量为 1，小于 3，且距离门限内不存在核心点，因此 $P_4$ 是噪声点。

样例2

输入

1 0 1
0 0

输出

0

说明

只有一个基站 $P_1(0,0)$。它到自身的曼哈顿距离为 $0$，在距离门限 $\epsilon_{dist}=0$ 内，所以空间邻域数量为 1。

由于 $MinPts$ 为 1，数量 1 不小于 1，因此 $P_1$ 是核心点，输出 0。

样例3

输入

2 0 2
0 0
1 1

输出

2
2

说明

共有 2 个基站，距离门限 $\epsilon_{dist}$ 为 0，数量门限 $MinPts$ 为 2。当距离门限为 0 时，只有在相同坐标上的基站才会互相进入邻域。

$P_1(0,0)$ 与 $P_2(1,1)$ 的曼哈顿距离为 $|1-0|+|1-0|=2$，大于 0，所以每个基站的邻域内只有自身，数量均为 1。

由于 1 小于 2，两个基站都不是核心点，也不存在核心点，因此它们均为噪声点，依次输出 2、2。