0240. Broken Chessboard

Имя входного файла: broken.in
Имя выходного файла: broken.out
Ограничение по времени: 250 ms
Ограничение по памяти: 64 megabytes

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 file

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 file

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.

Example:

broken.inbroken.out
3 .................... .................... .................... .................... ........A........... .................... ...............C.... .................... ..........B......... .................... .................... .................... .................... ............D....... ...........DDD...... ............D....... .................... .................... .................E.. .................... ADB DDD CDE


Источник: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Обсудить       Отправить решение



Версия для печати