Memory limit: 64 MB
The Byteland Army plans to conduct the greatest military exercise in its history this weekend. The exercise will take place on the training ground in Northern Bytetown. The officers of Byteland Army know this training ground perfectly; they do not, however, know the assignments. This is why they requested your help, recruit!
Your superiors know exactly where the strategic spots on the training ground are located. During the exercise they will be asked multiple times to capture various areas of the training ground. One of the most crucial decisions will be the allocation of forces and determining the strength needed to capture a particular area - this strength should be proportional to the number of strategic spots in the attacked area. Your task is to determine for each area, represented as a polygon with vertices in the strategic spots, the number of strategic spots lying strictly inside the interior of the area.
In the first line of the standard input two integers and are given (, ), denoting respectively the number of strategic spots on the training ground and the number of queries. The strategic spots are numbered from to .
The next lines give descriptions of the strategic spots. In the th line two integers and () are given, denoting the coordinates of the th strategic spot. No three strategic spots are collinear.
The next rows contain the descriptions of the queries. Each description begins with an integer (), denoting the number of vertices of the polygon. It is followed by different integers from the interval , which denote the identifiers of strategic spots that are subsequent vertices of the polygon. All the given polygons will be simple (i.e., without self-intersections), and their vertices are given in the clockwise order. The sum of all the numbers does not exceed .
Your program should write lines to the standard output. The th line should contain one integer, being the number of strategic spots in the interior of the polygon described in the th query.
For the input data:
6 4 0 0 0 5 5 0 11 10 5 5 2 1 4 1 2 4 3 4 1 2 5 3 3 6 2 4 3 1 2 6
the correct result is:
2 1 1 0
The circles in the figure depict strategic spots, while the numbers next to the circles - their identifiers. The figure shows the areas from the first (continuous lines) and third (dashed lines, filled in yellow) query.
Task author: Michal Pilipczuk.<Submit a solution> [0/10]