Point in Polygon

Input contains several test cases. Each test case begins with an integer $n$ ($3 \leq n \leq 1000$). Then follow the $n$ vertices of a simple polygon, one per line, each of the form $x\ y$. The points may be given in either clockwise or counterclockwise order. Then comes an integer $m$ ($m \leq 100$), giving the number of points to test, followed by $m$ lines, each containing a point in the same format as above. Coordinates are integers with absolute value bounded by 10000. The input is terminated by a case beginning with 0.

For each test case, output $m$ lines, one for each point to test.
The $i$:th output for a
test case should be one of “`in`”, “`out`”,
“`on`”, depending on whether the $i$:th test point lies inside,
outside, or on the given polygon.

Sample Input 1 | Sample Output 1 |
---|---|

3 0 0 10 0 0 10 3 4 5 5 5 6 5 5 41 -6 -24 -74 -51 -6 73 17 -30 -34 2 -12 -26 39 -8 0 |
in on out out in |