题目描述

在二维坐标平面上，存在一个凸 $N$ 边形 $S$，其中正向 $x$ 轴指向右边，正向 $y$ 轴指向上方。$S$ 的顶点按逆时针顺序给出，坐标分别为 $(X_1,Y_1),\\ldots,(X_N,Y_N)$。

对于每个点 $(A_i,B_i)$，回答以下问题：该点是在 $S$ 内部，外部，还是在 $S$ 的边界上？

约束条件

• $3 \\leq N \\leq 2\\times 10^5$
• $1 \\leq Q \\leq 2\\times 10^5$
• $\-10^9 \\leq X_i,Y_i,A_i,B_i \\leq 10^9$
• $S$ 是一个严格凸的 $N$ 边形，即其内角都小于 $180$ 度。
• $(X_1,Y_1),\\ldots,(X_N,Y_N)$ 是 $S$ 的顶点，按逆时针顺序给出。
• 输入中的所有值都是整数。

输入

从标准输入读入输入数据，格式如下：

$N$ $X_1$ $Y_1$ $\\vdots$ $X_N$ $Y_N$ $Q$ $A_1$ $B_1$ $\\vdots$ $A_Q$ $B_Q$

输出

输出包含 $Q$ 行。第 $i$ 行应该输出 IN，如果点 $(A_i,B_i)$ 在 $S$ 内部（不在边界上）；输出 OUT，如果点在 $S$ 外部（不在边界上）；输出 ON，如果它在 $S$ 的边界上。

示例输入 1

4
0 4
-2 2
-1 0
3 1
3
-1 3
0 2
2 0

示例输出 1

ON
IN
OUT

下图展示了 $S$ 和给定的三个点。第一个点在 $S$ 的边界上，第二个点在 $S$ 内部，第三个点在 $S$ 外部。

示例输入 2

3
0 0
1 0
0 1
3
0 0
1 0
0 1

示例输出 2

ON
ON
ON