The kingdom of 'Geometry Land' is huge and the number of people living here is also huge. One day, The King wanted to find how many people living in this kingdom. So, he asked all the inhabitants of the kingdom to stay in the kingdom for one day.
The kingdom can be modeled in a 2D plane as a convex polygon. The King sent many messengers to find all the people they can find. The messengers were not good at geometry, so, they noted the positions of the people as 2D co-ordinates using GPS.
Now you are given the map and the positions of the people of the kingdom. You have to find whether a person belongs to the kingdom or not. You can safely assume that the person is an inhabitant of the kingdom if and only if his position is inside the kingdom. If a person lies in the boundary of the map, you can consider him inside.
Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with a blank line and an integer n (3 ≤ n ≤ 105), denoting the number of vertices of the convex polygon that form the kingdom. Each of the next n lines will contain two integers: xi yi (-105 ≤ xi, yi ≤ 105) denoting the ith vertex of the polygon. The vertices will be given in anti-clockwise order.
The next line will contain an integer Q (1 ≤ Q ≤ 10000) denoting the number of positions reported by the messengers. Each of the next Q lines will contain two integers: xi yi (-105 ≤ xi, yi ≤ 105) denoting the position of the ith person.
Output
For each case, print the case number in a single line. Then for each reported person, print y or n depending whether the person is an inhabitant or not.
Sample
| Sample Input | Sample Output |
|---|---|
1 3 0 0 10 0 5 5 3 1 2 5 6 4 3 | Case 1: n n y |
Notes
Dataset is huge. Use faster I/O methods.