Pirate Bombs and Ships

There is an \(N\times M\) grid representing a sea. There are \(B\) bombs, each of which covers a rectangular area defined by its top‐left and bottom‐right coordinates \((r_1, c_1)\) and \((r_2, c_2)\) respectively. There are also \(S\) ships. Each ship is represented by two endpoints \((r_1, c_1)\) and \((r_2, c_2)\); if \(r_1=r_2\) then the ship is horizontal, and if \(c_1=c_2\) then it is vertical. A cell is considered covered if at least one bomb covers it. For each ship, output:

• MISS if none of its cells are covered;
• HIT if some (but not all) of its cells are covered; and
• SUNK if every cell of the ship is covered.

inputFormat

The first line contains four integers \(N\), \(M\), \(B\), and \(S\).
The next \(B\) lines each contain four integers \(r_1\), \(c_1\), \(r_2\), \(c_2\) representing the top‐left and bottom‐right coordinates of a bomb's area (the coordinates are 1-indexed).
The following \(S\) lines each contain four integers \(r_1\), \(c_1\), \(r_2\), \(c_2\) representing the two endpoints of a ship. It is guaranteed that either \(r_1=r_2\) (horizontal ship) or \(c_1=c_2\) (vertical ship).

outputFormat

Output \(S\) lines. The \(i\)-th line should be one of MISS, HIT, or SUNK according to the status of the \(i\)-th ship.

sample

5 5 1 3
2 2 4 4
1 1 1 3
2 3 2 5
3 3 3 3

MISS
HIT
SUNK