分割方格

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有一个m*m(m<=20)的方格纸,其中有n2个(n<=m,n<=6)方格标有“*”的记号,标有“*”的方格是连通的,所谓连通是指:假设有一个“车”在一个标有“*”的方格上,每次移动只能移到与原方格垂直相邻或水平相邻的标有“*”的方格上,经过有限次移动,“车”可以到达任意另一个标有“*”的方格,如图1所示。

现在要把这标有“*”的n2个方格分成A、B两部分,每部分都是连通的,而且,这两个部分经过旋转、翻转或平移后可以拼成n*n的正方形(若有多解,请给出任意一个)。

例如图1所示的例子,可以分成如下两部分如图7.2所示,并且这两部分可以拼成4*4的正方形如图7.3所示。 



 

Input

输入数据的第一行有一个整数m。以下m行每行各有m个字符:“.”代表空格,“*”代表标有“*”记号的方格。

Output

输出数据共有m行,每行有m个字符:“.”代表空格,“A”、“B”分别代表分割成的两部分的组成方格。

Sample Input

8
**..**..
**..**..
********
........
........
........
........
........

Sample Output

AA..BB..
AA..BB..
AAAABBBB
........
........
........
........
........

Hint

Source