National Olympiad in Informatics, China, 2005

The wisdom beads game set consists of a triangular board and ~12~ game pieces of varying shapes. The board is depicted in Figure 1, as follows:

Figure 1

The ~12~ game pieces fall into ~3~ major categories, depending on the number of beads they consist of.

For the 1st major category, there are ~3~ beads, but only one type of shape:

The symbol is ~A~, the shape is

For the 2nd major category, there are ~4~ beads and ~3~ types of shapes:

The symbol is ~B~, the shape is

The symbol is ~C~, the shape is

The symbol is ~D~, the shape is

For the 3rd major category, there are ~5~ beads and ~8~ types of shapes:

The symbol is ~E~, the shape is

The symbol is ~F~, the shape is

The symbol is ~G~, the shape is

The symbol is ~H~, the shape is

The symbol is ~I~, the shape is

The symbol is ~J~, the shape is

The symbol is ~K~, the shape is

The symbol is ~L~, the shape is

Figure 2

Figure 2 depicts one method of piecing together the game board. The depiction in Figure 2 can be simplified to Figure 3, so the board can be expressed as a two-dimensional array of characters.

B
B  K
B  K  K
B  J  K  K
J  J  J  D  D
G  J  G  D  D  C
G  G  G  C  C  C  I
E  E  E  H  H  I  I  A
E  L  H  H  H  I  A  A  F
E  L  L  L  L  I  F  F  F  F

A piece may be placed at any location on the board, provided that there is room to place it, and that the dimensions are appropriate. Rotations (~0^\circ~, ~90^\circ~, ~180^\circ~, and ~270^\circ~) and flips (horizontal and vertical) are allowed for placing any of the pieces.

Given the initial setup of a game board, determine a valid method for placing all of the remaining pieces onto the board.

Input Specification

The input contains a total of ~10~ lines, describing the initial game board. Line ~i~ contains ~i~ characters. If the ~j~-th character of line ~i~ is a letter from A to L, then that means row ~i~ column ~j~ has already been occupied by the game piece of the specified letter. If the ~j~-th character of line ~i~ is the character ., then that means row ~i~ column ~j~ is currently empty.

Output Specification

If it's possible to find a solution, print ~10~ lines to the output - the game board after all ~12~ pieces have been placed. The ~i~-th line must contain ~i~ characters, where the ~j~-th character of the ~i~-th line is the symbol of the piece that occupies the board at that location.
If there's no solution, output a single line with the string No solution.
The data guarantees that there will be at most one solution for each test case.

Sample Input

.
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........

Sample Output

B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF

Problem translated to English by Alex.