H. Do you love HIAST?
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$\textit{ALBaath University}$$$ is hosting a competitive programming contest under the ICPC rules, and things were going great until the competitors hit some hard problems. Suddenly, they were in desperate need of some reinforcements, and some teams from other universities agreed to help them out.

But wait! Uh-oh, it turns out that outside help is strictly forbidden in this contest. $$$\textit{HIAST (Hilarious Institute for the Advanced Study of Trickery) }$$$ heard about this and sent a special team to surround the university. Its mission is to catch any team from outside that might have sneaked in.

$$$\textbf{HIAST}$$$ is tricky. It gave you the problem to solve it so It can catch your allies. Now, it's up to you if you want to sacrifice your allies just to get the problem accepted.

You are given a polygon of $$$n$$$ vertices and $$$q$$$ queries.

Each query consists of a point $$$(x,y)$$$ and you have to check if it is inside (including the borders) or outside the polygon.

The points of the polygon are given in clockwise order with the property that either $$$x_i = x_{i-1}$$$ or $$$y_i = y_{i-1}$$$ (but not both), indicating that the edges are parallel to either the $$$x$$$- or $$$y$$$-axis, Also no two edges intersect (endpoints are not considered into the intersections).

Input

The first line of the input contains an integer $$$n$$$ $$$(4 \leq n \leq 10^5)$$$, representing the number of vertices in the polygon.

The next $$$n$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ $$$(0 \leq x_i, y_i \leq 10^6)$$$, representing the $$$x$$$- and $$$y$$$-coordinates, respectively, of the $$$i$$$-th vertex of the polygon in clockwise order.

The next line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$, representing the number of queries.

The next $$$q$$$ lines each contain two integers $$$x$$$ and $$$y$$$ $$$(0 \leq x, y \leq 10^6)$$$, representing the $$$x$$$- and $$$y$$$-coordinates, respectively, of a point to be checked whether it is inside or outside the polygon.

Output

Output $$$q$$$ lines, where each line contains either "YES" or "NO" (without quotes), indicating whether the corresponding query point is inside or outside the polygon, respectively.

Please Note that the answer is CaSe SeNsiTiVe so print the answer (YES/NO) with capital letters.

Example
Input
10
3 3
3 8
8 8
8 6
6 6
6 4
12 4
12 12
2 12
2 3
15
4 6
5 5
7 3
2 14
3 3
8 13
6 10
10 10
3 6
7 4
10 6
9 8
1 13
8 5
3 9
Output
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
Note

The polygon and the queries for the first test: