{$APPTYPE CONSOLE}

uses
  Types;

type
  TSnake = class
    head, tail: TPoint;
    dir: Integer;
    procedure Get(x, y: Integer);
    procedure Move;
  end;

const
  dx: array [0..3] of Integer = (1, 0,-1, 0);
  dy: array [0..3] of Integer = (0,-1, 0, 1);

var
  a: array of array of Char;
  p: array of array of Integer;

  procedure MoveXY(var x, y: Integer);
  var
    dir: Integer;
  begin
    dir := p[x, y];
    Inc(x, dx[dir]); Inc(y, dy[dir]);
  end;
  
  procedure TSnake.Get(x, y: Integer);
    var
      ch, chL: Char;

    function SnakeCell: Boolean;
    var
      i: Integer;
    begin
      Result := true;
      for i := 0 to 3 do
        if a[x + dx[i], y + dy[i]] = chL then begin
          p[x + dx[i], y + dy[i]] := i xor 2;
          if dir < 0 then dir := i xor 2;
          Inc(x, dx[i]); Inc(y, dy[i]);
          a[x, y] := ch;
          exit;
        end;
      tail := Point(x, y);
      while (x <> head.x) or (y <> head.y) do begin
        a[x, y] := chL;
        MoveXY(x, y);
      end;
      Result := false;
    end;
  begin
    if head.x > 0 then Halt(239);
    ch := a[x, y];
    chL := Chr(Ord(ch) - Ord('A') + Ord('a'));
    head.x := x; head.y := y;
    dir := -1;
    while SnakeCell do;
  end;

  procedure TSnake.Move;

    function TryMove(d: Integer): Boolean;
    var
      ch: Char;
    begin
      Result := a[head.x + dx[d], head.y + dy[d]] = '.';
      if not Result then exit;
      ch := a[head.x, head.y];
      a[head.x, head.y] := Chr(Ord(ch) - Ord('A') + Ord('a'));
      p[head.x, head.y] := d;
      MoveXY(head.x, head.y);
      a[head.x, head.y] := ch;
      a[tail.x, tail.y] := '.';
      MoveXY(tail.x, tail.y);
      dir := d;
    end;

  begin
    if head.x = 0 then exit;
    if TryMove(dir) or TryMove((dir + 1) mod 4) or TryMove((dir + 3) mod 4) then;
  end;

var
  snakes: array ['A'..'Z'] of TSnake;
  i, j, N, turns: Integer;
  f: TextFile;
  s: String;
  ch: Char;
begin
  Readln(N, turns);
  SetLength(a, N + 2, N + 2);
  SetLength(p, N + 2, N + 2);
  for j := 0 to N + 1 do begin
    a[0, j] := '#';
    a[N + 1, j] := '#';
  end;
  for i := 1 to N do begin
    Readln(s);
    for j := 1 to N do a[i, j] := s[j];
    a[i, 0] := '#'; a[i, N + 1] := '#';
  end;
  for ch := 'A' to 'Z' do
    snakes[ch] := TSnake.Create;
  for i := 1 to N do
    for j := 1 to N do
      if a[i, j] in ['A'..'Z'] then
        snakes[a[i, j]].Get(i, j);
  for i := 1 to turns do
    for ch := 'A' to 'Z' do
      snakes[ch].Move;
  for i := 1 to N do begin
    for j := 1 to N do
      Write(a[i, j]);
    Writeln();
  end;
end.
