Battleship

문제

You are in a computer security business. Recently one of your clients developed a new test designed to separate humans from programs. Your task is to test its efficiency.

The test is based on a variation of the Battleship game. This game is played on a ten by ten grid. Before the beginning of the test, you should place ten ships on this grid. Each ship is represented by a number of consecutive cells, arranged vertically or horizontally. You should place exactly one four-cell ship, two three-cell ships, three two-cell and four one-cell ships. No two ships should have any common or adjacent cells. They should not share a corner of a cell as well.

After the ships have been arranged, the test proceeds in a number of rounds. At each round one cell is announced to be “shot”. If this cell is occupied by a ship, this ship is considered to be “hit”. After each cell of a ship has been hit at least once, the ship sinks. The test ends after all the ships have sunk.

Let’s call the complexity of an arrangement the number of round it took to finish the tests. The idea is that humans would create much more complex arrangements than programs.

You have already figured out that the cells are shot in a predefined order, each cell being shot exactly once. Now you want to write a program that would create the most complex arrangement on the basis of the order in which the cells are shot.

입력

The input file consists of ten lines, containing ten numbers each. Each number represents the round at which the corresponding cell will be shot. All numbers are distinct and belong to the range 1 ... 100.

출력

Output the optimal ship arrangement for the battleship test. Empty cells should be represented by the dot (‘.’), occupied cells should by represented by the number sign (‘#’).

1 2 3 4 5 6 7 8 9 10
36 37 38 39 40 41 42 43 44 11
35 64 65 66 67 68 69 70 45 12
34 63 84 85 86 87 88 71 46 13
33 62 83 96 97 98 89 72 47 14
32 61 82 95 100 99 90 73 48 15
31 60 81 94 93 92 91 74 49 16
30 59 80 79 78 77 76 75 50 17
29 58 57 56 55 54 53 52 51 18
28 27 26 25 24 23 22 21 20 19

...####...
..........
#....##...
#.#.....#.
........#.
...###....
.#........
........#.
..#.....#.
.....#..#.