K. Pirates
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Help!

On your way to the AGM(Annual Galley Meeting) you are under attack by pirates trying to destroy your ship.

The way these pirates operate is quite different from what you would usually expect: they do not shoot at you with cannons, but rather bomb entire regions of the ocean. Furthermore, the captain of the ship does not use the usual Arrr!, but rather yells Yeey! or Ooh! whenever a ship is successfully hit or not. Truly bizzare.

Luckily for you, the pirates always operate the same way, so you already know the regions that will be bombed before the trip. This way you can plan how big of a ship to embark on and what route to pick!

The region you will be passing through is a rectangular grid with $$$N$$$ rows and $$$M$$$ columns.

You know that there are $$$B$$$ axis-aligned rectangular areas inside this grid that have been bombed.

Your ship can be thought of as a sequence of consecutive cells in the same line or column of the grid.

For $$$S$$$ placements of the ship, you would like to know the state of the ship after the bombing. The state can be one of the following:

  • MISS, if none of the cells of the ship was hit by a bomb.
  • HIT, if at least one of the cells of the ship was hit by at least a bomb.
  • SUNK, if every cell of the ship was hit by at least a bomb.
Input

The first line contains integers $$$N$$$ and $$$M$$$, the dimensions of the grid. It is guaranteed that $$$1 \leq N, M \leq 10^5$$$.

The next line contains integer $$$B$$$, the number of bombs. It is guaranteed that $$$1 \leq B \leq 2*10^5$$$.

The next $$$B$$$ lines each contain integers $$$x1$$$, $$$y1$$$, $$$x2$$$, $$$y2$$$ describing a bombed rectangular area between cells $$$(x1, y1)$$$ and $$$(x2, y2)$$$. It is guaranteed that $$$1 \leq x_1 \leq x_2 \leq N$$$ and $$$1 \leq y_1 \leq y_2 \leq M$$$. The bombs can overlap.

The next line contains integer $$$S$$$, the number of ships whose status we would like to know. It is guaranteed that $$$1 \leq S \leq 2*10^5$$$.

Each of the next $$$S$$$ lines contains a description of a ship:

  • 1 $$$l$$$ $$$c_1$$$ $$$c_2$$$, meaning there is a horizontal ship on line $$$l$$$ between columns $$$c_1$$$ and $$$c_2$$$. It is guaranteed that $$$1 \leq l \leq N$$$ and $$$1 \leq c_1 \leq c_2 \leq M$$$.
  • 2 $$$c$$$ $$$l_1$$$ $$$l_2$$$, meaning there is a vertical ship on column $$$c$$$ between lines $$$l_1$$$ and $$$l_2$$$. It is guaranteed that $$$1 \leq c \leq M$$$ and $$$1 \leq l_1 \leq l_2 \leq N$$$.

The placements of the ships can intersect each other.

Output

The output file should contain $$$S$$$ lines, each with the state of the corresponding ship.

Example
Input
5 5
3
2 1 2 2
2 2 3 3
3 4 5 4
5
1 2 1 3
1 2 1 4
2 1 3 5
1 3 2 4
2 2 1 5
Output
SUNK
HIT
MISS
SUNK
HIT