该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在平面直角坐标系中，以 $x$ 轴正方向为右，$y$ 轴正方向为上，有一个凸 $N$ 角形 $S$。$S$ 的顶点坐标按逆时针顺序是 $(X_1,Y_1),\ldots,(X_N,Y_N)$。

对于 $Q$ 个点 $(A_i,B_i)$，分别判断它们位于 $S$ 的内部、外部还是边界上。

输入格式

输入按照以下格式从标准输入提供：

N X_1 Y_1 ... X_N Y_N Q A_1 B_1 ... A_Q B_Q

输出格式

输出 $Q$ 行。对于第 $i$ 行，如果 $(A_i,B_i)$ 位于 $S$ 的内部（不包括边界），则输出 IN；如果位于外部（不包括边界），则输出 OUT；如果位于边界上，则输出 ON。

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

ON
IN
OUT

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

ON
ON
ON

提示

约束条件

• $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$ 的顶点。
• 所有输入值都是整数。

示例解释 1

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