Voronoi Diagram Point Query

Figure: Voronoi diagram of size 4.

In the 2-dimensional Cartesian coordinate system, we define the Voronoi diagram of a non-empty set of points $S$ as a diagram that divides the plane by the criterion "which point in the set $S$ is closest at this location?". More precisely, the Voronoi diagram of a given non-empty point set $\{P_1,\ P_2,\ \cdots,\ P_n\}$ is a collection of regions: a point $K$ is included in region $i$ if and only if $d(P_i,\ K) \le d(P_j,\ K)$ holds for all $1 \le j \le n$, where $d(X,\ Y)$ is the Euclidean distance between points $X$ and $Y$.

For example, in the picture above, every location on the plane is colored by the closest point to that location. Points that belong to a single region are colored with a light color indicating that region, and points that belong to more than one region form lines and points colored black.

There is an algorithm that computes the Voronoi diagram in $\mathcal{O}(n \log(n))$, but it is infamous for being very complicated and difficult. We are lenient problem setters, so we set $n \leq 2000$, which means you can solve this task with slower Voronoi diagram algorithms.

In this task, you should solve the point query problem in a Voronoi diagram: in the Voronoi diagram constructed from the point set $\{P_1,\ P_2,\ \cdots,\ P_n\}$, you should determine which region(s) the point belongs to. More precisely, you are given $q$ point queries. For each query point, you should determine the following:

• If it is not included in any region, output NONE.
• If it is included in exactly one region, output REGION X, where $X$ is the index of that region.
• If it is included in exactly two regions, output LINE X Y, where $X$ and $Y$ ($X$ < $Y$) are the indices of those two regions.
• If it is included in three or more regions, output POINT.

The first line gives the number of points forming the Voronoi diagram, $n$, and the number of queries, $q$. ($3 \le n \le 2,000,\ 1 \le q \le 250,000$)

The $i$-th of the next $n$ lines gives two integers indicating the $x$ and $y$ coordinates of $P_i$. These are the points that form the Voronoi diagram. All $n$ points are distinct. ($|x|,\ |y| \le 10,000$)

The $j$-th of the next $q$ lines gives two integers indicating the $x$ and $y$ coordinates of $Q_j$. For each point $Q_j$, you should determine which region(s) it belongs to. ($|x|,\ |y| \le 10,000$)

The output consists of $q$ lines. In the $j$-th line, print one of the following:

• If $Q_j$ is not included in any region, output NONE.
• If $Q_j$ is included in exactly one region, output REGION X, where $X$ is the index of that region.
• If $Q_j$ is included in exactly two regions, output LINE X Y, where $X$ and $Y$ ($X$ < $Y$) are the indices of those two regions.
• If $Q_j$ is included in three or more regions, output POINT.