33880번 - Лягушки на болоте 서브태스크다국어

В Сочи при подготовке Олимпиады-2014 была завезена самшитовая огнёвка (небольшая бабочка с Дальнего Востока). Она уничтожила самшитовую рощу, поэтому древесным лягушкам теперь приходится жить на болоте. Но они сохранили способность после прыжка менять свой цвет с зелёного на коричневый и наоборот.

Болото представляет собой плоскость, в некоторых точках которой располагаются кочки. Размером кочек можно пренебречь и считать их точками на плоскости. За один прыжок лягушка может перепрыгнуть с кочки, на которой она находится, на любую другую кочку, которая находится от неё на расстоянии не более $r$. После каждого прыжка цвет лягушки меняется на противоположный. Прыгать на месте лягушка не умеет.

Вам необходимо для каждой стартовой кочки лягушки от $1$ до $n$ определить, может ли она, совершив некоторое количество прыжков, вернуться на стартовую кочку, поменяв при этом свой цвет.

Первая строка содержит два целых числа $n$ и $r$ ($2 \le n \le 10^5$, $ 1 \le r \le 10^9$) --- число кочек на болоте и расстояние, на которое прыгает лягушка.

Каждая из следующих $n$ строк описывает расположение кочек. В $i$-й из них содержатся два целых числа $x_i$ и $y_i$ ($0 \le x_i, y_i \le 5 \cdot 10^8$) --- координаты $i$-й кочки.

Никакие две кочки не располагаются в одной точке.

Выведите строку, состоящую из $n$ символов. Если лягушка, стартовав с кочки $i$, может вернуться на неё, имея противоположный цвет, $i$-й символ должен быть <<1>>, а иначе --- <<0>>.

Прыжки, которые позволяют лягушке поменять цвет, начав с первой кочки, показаны на рисунке ниже.