AT_abc296_g [ABC296G] Polygon and Points

[problemUrl]: https://atcoder.jp/contests/abc296/tasks/abc296_g $ x $ 軸の正の向きを右、$ y $ 軸の正の向きを上とする $ 2 $ 次元座標平面上に、凸 $ N $ 角形 $ S $ があります。$ S $ の頂点の座標は、反時計回りに $ (X_1,Y_1),\ldots,(X_N,Y_N) $ です。 $ Q $ 個の点 $ (A_i,B_i) $ について、それぞれ $ S $ の内部・外部・境界上のいずれにあるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ Y_1 $ $ \vdots $ $ X_N $ $ Y_N $ $ Q $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_Q $ $ B_Q $

$ Q $ 行出力せよ。$ i $ 行目には、$ (A_i,B_i) $ が $ S $ の内部(境界含まず)にあるとき `IN`、外部(境界含まず)にあるとき `OUT`、境界上にあるとき `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 $ の頂点を反時計回りに列挙したものである。 - 入力は全て整数である。 ### Sample Explanation 1 $ S $ 及び 与えられた $ 3 $ 個の点は下図の通りです。$ 1 $ 番目の点は $ S $ の境界上、$ 2 $ 番目の点は内部、$ 3 $ 番目の点は外部にあります。 !\[図\](https://img.atcoder.jp/abc296/828da6ca52e6b48a908ad06fa59eb9cb.png)