P9284 [AGM 2023 Qualifier] Pirates

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.

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 $S$ lines. For each ship, output the answer.

Translated by ChatGPT 5