// (C) Timofey S. Chistyakov 2005

{$apptype console}

uses
  Math, Types;

const
  DI: array [1..4] of integer = (1, 0, -1, 0);
  DJ: array [1..4] of integer = (0, 1, 0, -1);
  REV_DIR: array [1..4] of integer = (3, 4, 1, 2);
  RIGHT_DIR: array [1..4] of integer = (4, 1, 2, 3);
  LEFT_DIR: array [1..4] of integer = (2, 3, 4, 1);
  
type
  TPos = packed record
    I, J: smallint;
  end;

  TSnake = record
    Letter: char;
    Dir: integer;
    Len, Cnt: integer;
    Snake: array of TPos;
    HeadIdx: integer;
  end;

var
  n, t: integer;
  terr: TStringDynArray;
  snakes: array ['A'..'Z'] of TSnake;


function LowCase(Ch: char): char;
begin
  Result := Char(Ord(Ch) + Ord('a') - Ord('A'));
end;


procedure RecognizeSnake(var Snake: TSnake; AI, AJ: integer);

  function doRec(CountOnly: boolean): integer;
  var
    i, j: integer;

    procedure add(Dir: integer);
    begin
      if (not CountOnly) then begin
        Snake.Snake[Result].I := i;
        Snake.Snake[Result].J := j;
      end;
      if (Result = 1) then
        Snake.Dir := REV_DIR[Dir];
      Inc(Result);
    end;
    
  var
    ni, nj, pi, pj, k, bk: integer;
  begin
    i := AI;   j := AJ;
    Result := 0;
    add(0);
    pi := -1;  pj := -1;
    while true do begin
      bk := 0;
      for k := 1 to 4 do begin
        ni := i + DI[k];
        nj := j + DJ[k];
        if
          ((ni <> pi) or (nj <> pj)) and (UpCase(terr[ni, nj]) = Snake.Letter)
        then begin
          Assert(bk = 0);
          bk := k;
        end;
      end;
      if (bk = 0) then
        Break; 
      pi := i; pj := j;
      i := i + DI[bk];
      j := j + DJ[bk];
      add(bk);
    end;
  end;

begin
  Snake.Len := doRec(true);
  Assert(Snake.Len >= 2);
  SetLength(Snake.Snake, Snake.Len);
  doRec(false);
end;


procedure MakeTurn(var Snake: TSnake);

  function tryIt(ADir: integer): boolean;
  var
    ni, nj: integer;
    tailIdx: integer;
  begin
    with Snake.Snake[Snake.HeadIdx] do begin
      ni := I + DI[ADir];
      nj := J + DJ[ADir];
    end;
    if (terr[ni, nj] = '.') then begin
      tailIdx := (Snake.HeadIdx + Snake.Len - 1) mod Snake.Len;
      terr[Snake.Snake[tailIdx].I, Snake.Snake[tailIdx].J] := '.';
      with Snake.Snake[Snake.HeadIdx] do
        terr[I, J] := LowCase(Snake.Letter);
      Snake.HeadIdx := tailIdx;
      with Snake.Snake[tailIdx] do begin
        I := ni;
        J := nj;
      end;
      terr[ni, nj] := Snake.Letter;
      Snake.Dir := ADir;
      Result := true;
    end
    else
      Result := false;
  end;

begin
  with Snake do
    if not tryIt(Dir) then
      if not tryIt(RIGHT_DIR[Dir]) then
        tryIt(LEFT_DIR[Dir]);
end;


var
  fi, fo: textfile;
  i, j: integer;
  ch: char;
begin
  ReadLn(n, t);

  Assert(InRange(n, 1, 1000));
  Assert(InRange(t, 1, 1000000));

  SetLength(terr, n + 2);
  terr[0] := StringOfChar('#', n + 2);
  terr[High(terr)] := StringOfChar('#', n + 2);
  for i := 1 to n do begin
    ReadLn(terr[i]);
    Assert(Length(terr[i]) = n);
    terr[i] := '#' + terr[i] + '#'; 
  end;

  for ch := 'A' to 'Z' do
    snakes[ch].Letter := #0;

  for i := 1 to n do
    for j := 2 to n + 1 do begin
      Assert(terr[i, j] in ['A'..'Z', 'a'..'z', '#', '.']);
      if terr[i, j] in ['A'..'Z'] then begin
        with snakes[terr[i, j]] do begin
          Assert(Letter = #0);
          Cnt := 0;
          Letter := terr[i, j];
          HeadIdx := 0;
        end;
        RecognizeSnake(snakes[terr[i, j]], i, j);
      end;
    end;

  for i := 1 to n do
    for j := 2 to n + 1 do
      if terr[i, j] in ['A'..'Z', 'a'..'z'] then begin
        Assert(snakes[UpCase(terr[i, j])].Letter <> #0);
        Inc(snakes[UpCase(terr[i, j])].Cnt);
      end;

  for ch := 'A' to 'Z' do
    Assert(snakes[ch].Len = snakes[ch].Cnt);

  for i := 1 to T do
    for ch := 'A' to 'Z' do
      if (snakes[ch].Letter <> #0) then
        MakeTurn(snakes[ch]);

  for i := 1 to n do
    WriteLn(Copy(terr[i], 2, n));
    
end.
