PRLGAME - A Game of Pearls

The game of pearls is to use the following 12 kinds of pearl designs each one and only one time to make the big pearl design.The pearl designs can be rotated and turned over arbitrarily. See the pictures below.


                   The empty grids



                  A sample big pearl design



A sample big pearl design used characters instead of colors



          Part A



          Part B



          Part C



          Part D



          Part E



          Part F



          Part G



          Part H



          Part I



          Part J



          Part K



          Part L



Input

Ten test cases(given one after another,you have to process all!), Each contains a big design, 'A'-'L' denote the filled grids, '.' denotes the empty grids,see the example. You can assume that the pearl designs used are completely put into the empty grids.

Output

A big design which has no grids that haven't been filled and each pearl design is used one and only one time in it,or 'No solution'(without quotes) if there's no solution.If there are multiple solutions,output any.

Example

Input:
.
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........
[and 9 test cases more]

Output:
B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF
[and 9 test cases more]

Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 2005,Day 1; translated by Blue Mary

hide comments
2016-03-11 03:22:44
can u check ur test cases? i got AC when i submit it in wcipeg.
2010-07-15 07:51:48 ymGXX
20s?It's too long!My program is very slow,but still get AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.