243. Broken Chessboard

time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



Chessboard with length of a side N was broken into K pieces, each of them is presented as a connected area (in this case connected area means such subset of chessboard cells, that there is a path of rook from any of them to any other).
These pieces were scattered all over the table (maybe rotated by 90, 180 or 270 degrees). Your task is to reconstruct chessboard again (position of black and white cells doesn't matter).
It is guaranteed that it is possible to construct square with side N from pieces given to you using all pieces.

Input
First line contains only one natural number N (1<=N<=5) - length of a side of the chessboard (in cells). Following 20 lines contain initial table description, each of these lines contains 20 characters. Empty place at the table is coded as "." character, and cells occupied by i-th piece of the chessboard are coded as i-th alphabet capital Latin letter.

Output
You must output N lines of N characters - constructed square chessboard with side N. Areas presented by i-th piece must be filled i-th in order of alphabet capital Latin letter and correspond to source image of pieces (maybe rotated by 90, 180, or 270 degrees). If there are several solutions, print any one of them.

Sample test(s)

Input
3
....................
....................
....................
....................
........A...........
....................
...............C....
....................
..........B.........
....................
....................
....................
....................
............D.......
...........DDD......
............D.......
....................
....................
.................E..
....................

Output
ADB
DDD
CDE
[submit]
[forum]

Author:Dmitry Filippov
Resource:SPbETU Training. DEF's contest
Date:November, 2003











Server time: 2017-11-24 13:57:32Online Contester Team © 2002 - 2016. All rights reserved.