#include"stdio.h"
#include"iostream"
struct snake
{
	int body[300][2] , dir , h , t , l , active ;
}S[26] ;
int d[4][2]={ {-1,0} , { 0 , 1 } , { 1 , 0 } , { 0 , -1 } } ;
int N , T ;
char box[1010][1010] , visited[1010][1010] ;
void input()
{
   int i ;
   scanf("%d%d",&N,&T);
   for( i=1 ; i<=N ; i++ )
	   scanf("%s",&box[i][1] ) ;
   for( i=0 ; i<=N+1 ; i++ )
   {
	   box[0][i]='#' ; box[N+1][i]='#';
	   box[i][0]='#' ; box[i][N+1]='#'; 
	   box[i][N+2]='\0' ;
   }
   memset( visited , 0 , sizeof( visited ) ) ;
   for( i=0 ; i<26 ; i++ ) S[i].active=0 ;
}
void get_s( int si , int sj , int k )
{
   visited[si][sj]=k + 'a' ;
   if( visited[si-1][sj]!=k+'a' && box[si-1][sj]-'a' == k )
   {
      S[ k ].body[ S[k].t+1 ][0]=si-1 ;
	  S[ k ].body[ S[k].t+1 ][1]=sj ;
	  S[k].t++;
	  get_s( si-1 , sj , k ) ; return  ;
   }
   if( visited[si+1][sj]!=k+'a' && box[si+1][sj]-'a' == k )
   {
      S[ k ].body[ S[k].t+1 ][0]=si+1 ;
	  S[ k ].body[ S[k].t+1 ][1]=sj ;
	  S[k].t++;
	  get_s( si+1 , sj , k ) ; return  ;
   }
   if( visited[si][sj-1]!=k+'a' && box[si][sj-1]-'a' == k )
   {
      S[ k ].body[ S[k].t+1 ][0]=si ;
	  S[ k ].body[ S[k].t+1 ][1]=sj-1 ;
	  S[k].t++;
	  get_s( si , sj-1, k ) ; return  ;
   }
   if( visited[si][sj+1]!=k+'a' && box[si][sj+1]-'a' == k )
   {
      S[ k ].body[ S[k].t+1 ][0]=si ;
	  S[ k ].body[ S[k].t+1 ][1]=sj+1 ;
	  S[k].t++;
	  get_s( si , sj+1 , k ) ; return  ;
   }
}
void get_d( int k )
{
	if( S[k].body[0][0]==S[k].body[1][0]-1 ) S[k].dir=0;
	else if( S[k].body[0][1]==S[k].body[1][1]+1 ) S[k].dir=1;
	else if( S[k].body[0][0]==S[k].body[1][0]+1 ) S[k].dir=2;
	else S[k].dir=3 ;
}
void scan()
{
	int i , j ;
	for( i=1 ; i<=N ; i++ )
		for( j=1 ; j<=N ; j++ )
		{
			if( box[i][j]>='A' && box[i][j]<='Z' ) 
			{
				S[ box[i][j]-'A' ].active=1;
				S[ box[i][j]-'A' ].h=S[ box[i][j]-'A' ].t=0 ;
				S[ box[i][j]-'A' ].body[0][0]=i;
				S[ box[i][j]-'A' ].body[0][1]=j;
				get_s( i , j , box[i][j]-'A' ) ;
				S[ box[i][j]-'A'].l = S[ box[i][j]-'A'].t ; 
				get_d(  box[i][j]-'A' ) ;
			}
		}
}
bool go( int k , int n)
{
	int f=(S[k].dir+n)%4  , nx , ny ;
	if( box[ S[k].body[ S[k].h ][0]+ d[f][0] ][ S[k].body[ S[k].h][1] + d[f][1] ]=='.' )
	{
	   S[k].dir=f ;
	   nx=S[k].body[ S[k].h ][0]+ d[f][0] ; ny=S[k].body[ S[k].h][1] + d[f][1] ;
       box[ S[k].body[ S[k].h ][0]+ d[f][0] ][ S[k].body[ S[k].h][1] + d[f][1] ]='A' + k ;
	   box[ S[k].body[ S[k].h ][0]          ][ S[k].body[ S[k].h][1]           ]='a' + k ;
       box[ S[k].body[ S[k].t ][0]          ][ S[k].body[ S[k].t][1]           ]='.'     ;
	   S[k].h--;
	   if( S[k].h<0 ) S[k].h=S[k].l ;
	   S[k].body[ S[k].h ][0] = nx ;
       S[k].body[ S[k].h ][1] = ny ; 
	   S[k].t--;
	   if( S[k].t<0 ) S[k].t=S[k].l ;
       return true ;
	}
	return false ;

}
bool moves( int k )
{
	if( go( k , 0 ) ) return true;
	if( go( k , 5 ) ) return true ;
	if( go( k , 3 ) ) return true ;
	return false ;
}
void output()
{
	int i , j ;
	for( i=1 ; i<=N ; i++ )
	{
		for( j=1 ; j<=N ; j++ )
			printf("%c",box[i][j] )  ;
		printf("\n") ;
	}
}
bool move()
{
	int i;
	bool r = false ;
	for( i=0 ; i<26 ; i++ )
	{
		if( S[i].active && moves( i ) ) r=true; 
	}
	return r ;
}
void run()
{
	int i ;
	for( i=0 ; i<T ; i++ )
	{
		if( !move() ) return ;
	}
}
int main()
{
	input();
	scan();
	run();
	output();
	return 0 ;
}