Battleship Game Simulation

Simulate a simple version of the classic Battleship game on a 5×5 grid. There is a single ship of length 3 placed either horizontally or vertically. The ship's placement is determined by the input: for horizontal placement, the ship occupies cells \( (r, c), (r, c+1), (r, c+2) \); for vertical placement, it occupies \( (r, c), (r+1, c), (r+2, c) \).

After the ship is placed, the game accepts a series of guesses provided as row and column coordinates. For each guess, output one of the following messages:

• Hit: if the guess hits a part of the ship (but does not sink it)
• Miss: if the guess does not hit any part of the ship
• Already Guessed: if the same cell is guessed more than once
• You sank the battleship!: when the final part of the ship is hit

The game automatically ends if 10 guesses have been made or if the ship is sunk. Once the ship is sunk, any subsequent guesses are ignored.

inputFormat

The input consists of the following lines:

1. The first line contains three integers: orientation, row, and col. The orientation is 0 for horizontal and 1 for vertical. For a horizontal ship it is guaranteed that col + 2 < 5; for a vertical ship, it is guaranteed that row + 2 < 5.
2. The second line contains an integer N (1 ≤ N ≤ 10), the number of guesses.
3. Each of the next N lines contains two integers: row and col, representing a guess (0-indexed).

outputFormat

For each guess, output one line containing one of the messages: "Hit", "Miss", "Already Guessed", or "You sank the battleship!". Once the ship is sunk, ignore any subsequent guesses.

## sample

0 1 1
3
1 1
1 2
1 3

Hit
Hit
You sank the battleship!

</p>