Battleships

Cindy and Charlie are playing a game of battleships.

If you’ve never played battleships before, it is a game with two players and two grids. Each player has their own grid which the other player cannot see. On each person’s grid are a series of different sized ships at different coordinates. Each player takes turns firing missiles at different coordinates to see if it will hit one of the other’s ships.

For example, Cindy might fire a missile at the coordinate (2, 3). Charlie then checks to see if any of his ships lie over those coordinates. He will then say 'Hit b' if Cindy has hits ship 'b', or 'Miss' if she missed.

Cindy thinks Charlie is not very good at getting the coordinates right. So she asks you to write a program that checks his grid for him!

Charlie would also like you to tell him when Cindy sinks one of his ships with the word 'Sunk' instead of 'Hit'. If 'a' is the name of the sunken ship, then print 'Sunk a'. This means that all coordinates ship 'a' occupied were hit.

Charlie will give you his 10 by 10 grid with some ships on it. Each ship is made from a letter in the alphabet from 'a' up to 'f'. Therefore, there are 6 ships in total. Ship 'a' is always 1 letter long, ship 'b' is always 2 letters long, ship 'c' takes 3 letters, and so on up to 'f'. Ships are made of horizontal or vertical lines of letters, but never diagonal. There is only ever one ship for each letter.

Cindy never guesses the same coordinate twice and she always guesses valid coordinates.

Input

The first 10 lines you read in will tell you about Charlie's grid. Each line will have 10 space separated characters. A hash symbol '#' indicates an empty coordinate on the grid. Part of a ship is indicated by its letter. See the examples below.

After these 10 lines, Cindy will then enter one pair of coordinates per line. These are 2 space separated integers, $x$ and $y$, for the coordinate of her next missile. Because we are talking about computers, the point (0, 0) refers to the top left corner of Charlie's grid, and the point (9, 9) is found at the bottom right. The $y$-axis increases in value down the screen, and the $x$-axis increases in value from left to right.

When Cindy enters the coordinate (-1 -1), your program should end.

Note that $0 \le x, y < 10$ except for the last line. This means that input is always valid, so don’t worry about unexpected input.

Output

For each coordinate that Cindy enters, there are three cases to consider:

• No ship is found at the coordinate, so print the word Miss on a single line (Don't forget the capital 'M').
• A ship occupies the coordinate, so output the word Hit followed by a space and then the letter of that ship. For example, if Cindy hits ship 'b' then print 'Hit b'.
• When all coordinates of the same letter have been hit, then that ship is said to be sunk. In this case, print Sunk followed by a space and then the letter of the ship that has sunk. For example, ship 'a' is always sunk on the first hit since it only occupies a single coordinate, so print 'Sunk a'.

Subtasks

Subtasks give your partial marks for getting certain components of the problem correct. This means you can still get marks if you don't know how to solve the full problem.

• Tell Cindy only if she hits or misses (sample 1) for 30%.
• Complete the first subtask, plus tell Charlie if one of his ships sinks. No ships will be touching each other (sample 2) for 50%.
• Give the complete solution for 100%.

Hints

• You can think of the grid as a list of rows. Your program will need a data structure that can hold sequenced data.
• Break the problem down into small steps. Try reading in the data first. Then add some code to tell Cindy if she hits or misses. This is known as a subtask which will give you partial marks if you submit it.
• How could you check if a ship has been sunk? Will your solution work when ships are right next to each other?
• Try thinking up some tricky tests for your program.
• Make sure you are using the correct coordinate system. Remember to start from zero.

Examples

Use the sample inputs below to test your program. Your program's output should look the same as the sample output. Think up some of your own tests too.

Sample 1

The coordinate (7, 1) hits the top of ship 'e', the next two coordinates do not hit any ships. At (3, 8) the second from left section of ship 'd' has been hit.

Sample 2

The first two coordinates (2, 4) and (3, 4) take out the left and middle sections of ship ‘c’. (4, 4) then sinks ship c so we print ‘Sunk c’. Ship ‘a’ at (4, 1) is sunk in one hit because it is only one unit long.