During the preparations for the 2014 Olympics in Sochi, the box tree moth (a small butterfly from the Far East) was introduced. It destroyed the boxwood grove, so tree frogs now have to live in a swamp. However, they have retained the ability to change their color from green to brown and vice versa after each jump.
The swamp is a plane, and there are hummocks at certain points. The size of the hummocks can be neglected, and they can be considered as points on the plane. In one jump, a frog can jump from the hummock it is currently on to any other hummock that is at a distance of no more than $r$ from it. After each jump, the frog's color changes to the opposite. A frog cannot jump to the same hummock it is currently on.
You need to determine for each starting hummock of the frog from $1$ to $n$ whether it can return to the starting hummock after making some number of jumps, having changed its color in the process.
Input
The first line contains two integers $n$ and $r$ ($2 \le n \le 10^5$, $1 \le r \le 10^9$) — the number of hummocks in the swamp and the distance the frog can jump.
Each of the following $n$ lines describes the location of the hummocks. The $i$-th line contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 5 \cdot 10^8$) — the coordinates of the $i$-th hummock.
No two hummocks are located at the same point.
Output
Output a string consisting of $n$ characters. If a frog, starting from hummock $i$, can return to it with the opposite color, the $i$-th character should be '1', otherwise '0'.
Scoring
| Subtask | Points | Additional Constraints | Required Subtasks |
|---|---|---|---|
| 1 | 10 | $n \le 3$ | |
| 2 | 20 | $n \le 200$ | 1 |
| 3 | 6 | $n \le 1\,000$ | 1, 2 |
| 4 | 9 | $n \le 10\,000$ | 1–3 |
| 5 | 16 | $y_i = 0$ | |
| 6 | 5 | $r \le 2$ | |
| 7 | 5 | $r \le 4$ | 6 |
| 8 | 5 | $r \le 10$ | 6, 7 |
| 9 | 12 | $(x_i - x_j)^2 + (y_i - y_j)^2 \ge \frac{r^2}{4}, i \neq j$ | 6 |
| 10 | 12 | 1–9 |
Examples
Input 1
6 5 4 1 4 4 1 5 5 9 9 6 10 2
Output 1
111000
Note
The jumps that allow the frog to change its color, starting from the first hummock, are shown in the figure below.
The jumps that allow the frog to change its color, starting from the first hummock, are shown in the figure below.