Gunshots

President Bartlet was shot! A group of terrorists shot to the crowd when President Bartlet waved to cheering people after his address. Many people were shot by the irrational bullets. Senior FBI agent Don Epps takes responsibility for this case. According to a series of crime scene investigation, including analyzing shot shells, replaying video from closed-circle television and collecting testimony by witnesses, Don keeps all the information about where and how the terrorists shot to crowd, as well as the location of every single person when the gun shoot happened. Now he wants to know how many gunshot victims are there in this case.

Imagine that each target person can be regarded as a polygon (can be concave or self-intersecting) and each gunshot can be regarded as a half-line. The bullet will be stopped by the first person it shoots. A person can be shot in three ways:

To simplify the problem, we assume that any two polygons can be completely separated by a line. Also each start point of the gunshot can be separated from each polygon by a line. Now given M people and N gunshots, please work out which person has been shot by each bullet.

There are multiple test cases in the input. The first line of the input file is an integer T demonstrating the number of test cases. (T<=10).

For each test case, the first line is an integer N, representing the number of people (polygons). Following lines demonstrates the polygons. For the ith polygon (0<=i<N), the first line is an integer Q_i, representing the number of edges of this polygon. In each of the following Qi lines, there are two real numbers x_i and y_i representing a point. Every pair of adjacent points demonstrate an edge of this polygon (i.e. (x_i, y_i) to (x_i+1, y_i+1) is an edge, in which 0<=i<Q_i-1), and (x_Qi-1, y_Qi-1) to (x₀, y₀) also demonstrates an edge of this polygon.

Then there is a line contains an integer M representing the number of gunshots. In the following M lines, each line contains four real numbers x, y, dx and dy, representing the start point (x, y) and direction vector (dx, dy) of that gunshot.

In all test cases, we assume that 0< N<=100, 0<Q_i<=1000, 0<M<=10000.

For each test case, output contains M lines and the i^th line demonstrates the result of the i^th gunshot.

If the i^th gunshot shoots the j^th polygon, the i^th line contains “HIT j”, otherwise it contains a word “MISS” (means that it does not shoot any target). The polygons are numbered in the order of their appearance in the input file, and the numbers start from 0.

At the end of each test case, please output a single line with “*****”.

1
1
4
0 0
1 1
0 1
1 0
2
-1 0 1 0
-2 0 -1 0

HIT 0
MISS
*****

The figure of the first case in the samples is as follows:

2010 Asia Hangzhou Regional Contest