「ROI 2025 Day2 T2」沼泽青蛙

题目描述

在索契筹备 $2014$ 年奥运会时，意外引入了来自远东的小型蝴蝶——箱树蛾。它毁掉了当地的箱树林，迫使树蛙们搬到了沼泽里生活。不过，这些聪明的树蛙依然保留了它们的神奇本领：每次跳跃后，它们的颜色会在绿色和棕色之间切换。

沼泽是一片平面，上面散布着许多小土丘，可以看作平面上的点。青蛙一次跳跃可以从当前土丘跳到任何一个距离不超过 $r$ 的其他土丘。跳跃后，青蛙的颜色会变成相反的颜色。需要注意的是，青蛙无法在原地跳跃。

你的任务是，对于从 $1$ 到 $n$ 的每个起始土丘，判断青蛙能否通过若干次跳跃回到这个土丘，并且在回到时颜色与初始时相反。

输入格式

第一行包含两个整数 $n$ 和 $r$ $(2 \le n \le 10^5, 1 \le r \le 10^9)$，分别表示沼泽中土丘的数量和青蛙的最大跳跃距离。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ $(0 \le x_i, y_i \le 5 \cdot 10^8)$，表示第 $i$ 个土丘的坐标。

保证任意两个土丘的坐标不重合。

输出格式

输出一个长度为 $n$ 的字符串，包含字符 0 或 1。如果从第 $i$ 个土丘开始的青蛙能回到该土丘且颜色相反，则第 $i$ 个字符为 1；否则为 0。

样例

输入

6 5
4 1
4 4
1 5
5 9
9 6
10 2

输出

111000

样例解释
下图展示了从第一个土丘开始，青蛙通过跳跃改变颜色的路径：

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。