The developers of Clash Royale are currently experimenting with the Mortar card. Rather than targeting the nearest enemy, Mortars target the closest enemy which is at least some distance $$$d$$$ away. For performance reasons, the developers define distance using Manhattan distance – in particular, the Manhattan distance between two points $$$(x, y)$$$ and $$$(x', y')$$$ is defined as $$$|x' - x| + |y' - y|$$$.
In their test simulation, the developers have $$$n$$$ of these Mortars numbered from $$$0$$$ to $$$n - 1$$$ on a two-dimensional grid, and for the purposes of testing, each Mortar considers all other Mortars to be enemies. However, the developers are struggling to efficiently compute which Mortar each Mortar will target, leading the simulation to stall. Can you help them compute the targets more efficiently?
Warning: Python solutions may struggle to pass test cases due to the time limit.
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le d \le 10^9$$$) – the number of Mortars and the minimum distance threshold, respectively.
The next $$$n$$$ lines each contain two integers, with the $$$i$$$-th line containing $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i \le 5 \cdot 10^8$$$, $$$0 \le y_i \le 5 \cdot 10^8$$$) – the x-coordinate and the y-coordinate of the $$$i$$$-th Mortar, respectively. The locations of the Mortars are not necessarily distinct.
Output $$$n$$$ space-separated integers, where the $$$i$$$-th integer is the number of the Mortar that the $$$i$$$-th Mortar will target. If the $$$i$$$-th Mortar has no target, output $$$-1$$$, and if there are multiple potential targets which are equally close to the Mortar, output the smallest numbered target.
4 40 02 22 14 0
1 0 -1 0
For the sample test case, Mortar $$$0$$$ can target Mortars $$$1$$$ and $$$3$$$. Since both are equally close, Mortar $$$0$$$ targets Mortar $$$1$$$. Applying a similar procedure to the other Mortars, it can be seen that Mortar $$$1$$$ targets Mortar $$$0$$$, Mortar $$$2$$$ does not have any target, and Mortar $$$3$$$ targets Mortar $$$0$$$.
| Name |
|---|


