Battleship Game Simulation

Your task is to implement a simulation of the Battleship game. The game is played on a square board of size \(n \times n\). Two players place ships on their respective boards and then take turns attacking positions on the opponent's board.

The game supports two operations:

• place: Place a ship on the board. The command provides the player number, the ship's length, the starting coordinate (row and column), and the orientation ('H' for horizontal and 'V' for vertical). The placement fails if the ship goes out of bounds or overlaps with an existing ship.
• attack: Attack a coordinate on the opponent's board. If an attack hits a ship, the cell is marked as hit ('H'); if the cell is empty, it is marked as missed ('M'). If an attack sinks the last ship of the opponent, the outcome should be "Player X wins!" where X is the attacking player's number.

Implement the game such that it reads input from stdin and writes the corresponding results to stdout.

inputFormat

The input is given from stdin in the following format:

 n
 q
 command_1
 command_2
 ...
 command_q

Here:

• n: an integer representing the board size (the board is \(n \times n\)).
• q: an integer representing the number of commands.
• Each command is on a separate line and is either:
• place p L r c O where p is the player number (1 or 2), L is the ship length, r and c are the row and column of the starting coordinate (0-indexed), and O is the orientation ('H' or 'V').
• attack p r c where p is the attacking player's number and r, c are the target coordinates (0-indexed).

outputFormat

For each command that requires an output, print a single line to stdout:

• For a place command, output True if the ship is successfully placed; otherwise, output False.
• For an attack command, output one of the following: Hit, Miss, or Player X wins! if the attack sinks the last ship of the opponent.

## sample

5
4
place 1 3 2 1 H
place 2 2 2 2 V
attack 1 2 2
attack 1 1 1

True
True
Hit
Miss

</p>