Description

The Smart Beads puzzle consists of a triangular board and 12 distinct pieces. The board is shown in Figure 1. Each piece, made of beads, can be placed at any position on the board as long as it fits and there is space for it. All pieces may be rotated by 0°, 90°, 180°, or 270°, and may be flipped horizontally or vertically. Given an initial layout of the board, find a valid arrangement that places all 12 pieces on the board.

Input Format

The file contains the initial board description in 10 lines. The i-th line has i characters. If the j-th character of the i-th line is a letter 'A' to 'L', then the cell at row i and column j is already occupied by a piece whose ID is that letter. If the j-th character is '.', then the cell at row i and column j is empty. The input guarantees that all pre-placed pieces are legally placed on the board.

Output Format

If a solution exists, print 10 lines describing the layout after placing all 12 pieces. The i-th line should contain i characters, and the j-th character of the i-th line indicates which piece occupies that cell. If there is no solution, print the single string No solution (without quotes, case-sensitive). All testdata guarantee that there is at most one solution.

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

B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF

Hint

Translated by ChatGPT 5