题目描述

在平面直角坐标系上给定一个 $n$ 个点的凸多边形，顶点均为整点，并按照逆时针顺序给出。

接下来有 $Q$ 个询问，每个询问给出一个整点，输出其是在多边形内部、外部或是边上。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x_i, y_i$。

接下来一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $a_i, b_i$。

输出格式

输出 $Q$ 行，每行一个字符串表示对应询问的答案。

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$。