题目背景

翻译自 CSES-2192 题。

题目描述

给定一个有 $n$ 个顶点的多边形和一组 $m$ 个点。你的任务是判断每个点是位于多边形内部、外部，还是在多边形的边界上。

这个多边形有 $n$ 个顶点 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$。对于每个 $i = 1, 2, \ldots, n-1$，顶点 $(x_i, y_i)$ 和 $(x_{i+1}, y_{i+1})$ 是相邻的，而顶点 $(x_1, y_1)$ 和 $(x_n, y_n)$ 也是相邻的。

输入格式

第一行输入两个整数 $n$ 和 $m$：分别表示多边形的顶点数和点的数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示多边形的第 $i$ 个顶点坐标。

接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示一个点的坐标。

输出格式

对于每个点，输出 INSIDE、OUTSIDE 或 BOUNDARY。

• INSIDE 表示该点位于多边形内部。
• OUTSIDE 表示该点位于多边形外部。
• BOUNDARY 表示该点在多边形的边界上。

样例

4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3

INSIDE
OUTSIDE
BOUNDARY

数据范围

• $3 \le n, m \le 1000$
• $-10^9 \le x_i, y_i \le 10^9$
• $-10^9 \le x,y \le 10^9$