#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=16,maxm=270;
char str[maxn][maxn+1],back_str[maxm][maxn][maxn+1];//str存原图,back表示备份数组
int state[maxn][maxn],back_state[maxm][maxn][maxn],cnt=0;//state[i][j]表示第i行第j列可填字母的二进制状态,cnt表示有几个空格
int ones[1<<maxn],turn[1<<maxn];//ones预处理所有状态中有几个一,turn预处理1在任意一位上表示几
inline int lowbit(int x)//取出最后一位1
{
return x&-x;
}
void work(int x,int y,int c)//填写字母
{
str[x][y]=c+'A';
for(int i=0;i<maxn;i++)
{
state[x][i]&=~(1<<c);//不可以用异或
state[i][y]&=~(1<<c);
}
int sx=x/4*4,sy=y/4*4;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
state[sx+i][sy+j]&=~(1<<c);
state[x][y]=(1<<c);//填上之后明显只有一种可能
}
bool dfs(int cnt)
{
if(!cnt) return 1;
int kcnt=cnt;//备份
memcpy(back_str[kcnt],str,sizeof(back_str[kcnt]));
memcpy(back_state[kcnt],state,sizeof(back_state[kcnt]));
//对于每一个空格,没有任何一个字母可以填上,无解
//有且只有一个字母可以填上,则直接填上
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
if(str[i][j]=='-')
{
int t=state[i][j];
if(!t)//当前状态没有字母可填,无解
{
memcpy(str,back_str[kcnt],sizeof(str));
memcpy(state,back_state[kcnt],sizeof(state));
return 0;
}
if(ones[t]==1)//只有一个字母可填,填上
{
work(i,j,turn[t]);
cnt--;
}
}
//对每一行来说,如果某个字母不能出现在任何一个位置,无解
//对某个字母,只能出现在一个位置,则直接填上
for(int i=0;i<maxn;i++)
{
int sor=0,sand=(1<<maxn)-1,drawn=0;
//sor表示一行里可选字母的并集
//sand表示一行里哪些字母只能填在某一个位置上
//drawn表示一行里哪些字母已经填上
for(int j=0;j<maxn;j++)
{
int t=state[i][j];//t是可选字母
sand&=~(t&sor);//t&sor表示这个格子可以填某个字母并且前面的格子也可以填
//取反之后与上sand表示这个字母不是只能填在一个位置上
sor|=t;//或也就是取并集
if(str[i][j]!='-') drawn|=t;//表示这个字母已经填上
}
if(sor!=(1<<maxn)-1)//如果有字母不能填,无解
{
memcpy(str,back_str[kcnt],sizeof(str));
memcpy(state,back_state[kcnt],sizeof(state));
return 0;
}
for(int j=sand;j;j-=lowbit(j))//枚举只能填在一个位置上的字母
{
int t=lowbit(j);
if(!(drawn&t))//这个可以填的字母之前没填上
for(int k=0;k<maxn;k++)
if(state[i][k]&t)//这个字母在这个位置上可以填
{
work(i,k,turn[t]);
cnt--;
}
}
}
//对每列,copy一下改改数组标号
for(int i=0;i<maxn;i++)
{
int sor=0,sand=(1<<maxn)-1,drawn=0;
for(int j=0;j<maxn;j++)
{
int t=state[j][i];
sand&=~(t&sor);
sor|=t;
if(str[j][i]!='-') drawn|=t;
}
if(sor!=(1<<maxn)-1)
{
memcpy(str,back_str[kcnt],sizeof(str));
memcpy(state,back_state[kcnt],sizeof(state));
return 0;
}
for(int j=sand;j;j-=lowbit(j))
{
int t=lowbit(j);
if(!(drawn&t))
for(int k=0;k<maxn;k++)
if(state[k][i]&t)
{
work(k,i,turn[t]);
cnt--;
}
}
}
//对每个宫格,仍然是改改标号
for(int i=0;i<maxn;i++)//i表示正在遍历第几个宫格
{
int sor=0,sand=(1<<maxn)-1,drawn=0;
for(int j=0;j<maxn;j++)//j表示正在遍历第i个宫格的哪个位置
{
int sx=i/4*4,sy=i%4*4,dx=j/4,dy=j%4;
int t=state[sx+dx][sy+dy];
sand&=~(t&sor);
sor|=t;
if(str[sx+dx][sy+dy]!='-') drawn|=t;
}
if(sor!=(1<<maxn)-1)
{
memcpy(str,back_str[kcnt],sizeof(str));
memcpy(state,back_state[kcnt],sizeof(state));
return 0;
}
for(int j=sand;j;j-=lowbit(j))
{
int t=lowbit(j);
if(!(drawn&t))
for(int k=0;k<maxn;k++)
{
int sx=i/4*4,sy=i%4*4,dx=k/4,dy=k%4;
if(state[sx+dx][sy+dy]&t)
{
work(sx+dx,sy+dy,turn[t]);
cnt--;
}
}
}
}
if(!cnt) return 1;
int x,y,minx=17;
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
if(str[i][j]=='-' && minx>ones[state[i][j]])//取可填字母最少的空格
{
minx=ones[state[i][j]];
x=i;y=j;
}
//这里不能备份str,因为下面深搜无解之后需要回溯到的状态是优化之前的状态
memcpy(back_state[kcnt],state,sizeof(back_state[kcnt]));//备份
for(int i=state[x][y];i;i-=lowbit(i))
{
memcpy(state,back_state[kcnt],sizeof(state));//恢复状态,深搜
work(x,y,turn[lowbit(i)]);
if(dfs(cnt-1)) return 1;
}
memcpy(str,back_str[kcnt],sizeof(str));//无解
memcpy(state,back_state[kcnt],sizeof(state));
return 0;
}
int main()
{
//预处理
for(int i=0;i<maxn;i++)
turn[1<<i]=i;
for(int i=0;i<(1<<maxn);i++)
for(int j=i;j;j-=lowbit(j))
ones[i]++;
//输入
while(cin>>str[0])
{
for(int i=1;i<maxn;i++)
cin>>str[i];
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
state[i][j]=(1<<maxn)-1;
int cnt=0;//遍历看空格数
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
if(str[i][j]!='-') work(i,j,str[i][j]-'A');
else cnt++;
dfs(cnt);
for(int i=0;i<maxn;i++)
cout<<str[i]<<endl;
cout<<endl<<endl;
}
return 0;
}