Problem Description

The pirates are in a rectangular sea area with $N$ rows and $M$ columns.

Next, there will be $B$ bombs. The area covered by each bomb is a rectangle.

The pirates have $S$ ships. Each ship is either several columns in one row, or several rows in one column. For each ship, you need to output:

MISS The ship is not covered by any bomb;

HIT The ship is covered by bombs, but not completely covered;

SUNK The ship is completely covered by bombs.

Input Format

The first line contains two positive integers $N,M(1\leq N,M\leq 10^5)$.

The next line contains one integer $B(1\leq B\leq 2\times 10^5)$.

The next $B$ lines each contain four positive integers $x1,y1,x2,y2(1\leq x1\leq x2\leq N,1\leq y1\leq y2\leq M)$, representing the bomb coverage area.

The next line contains one integer $S(1\leq S\leq 2\times 10^5)$.

The next $S$ lines each contain four positive integers $opt,c,l,r$. If $opt=1$, it means the $i$-th ship consists of columns $l$ to $r$ in row $c$. Otherwise, if $opt=2$, it means the ship consists of rows $l$ to $r$ in column $c$.

Ships may intersect with other ships, and bombs may intersect with other bombs.

Output Format

Output $S$ lines. For each ship, output the answer.

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

SUNK
HIT
MISS
SUNK
HIT

Hint

Translated by ChatGPT 5