Snake

Several snakes crawl over a board of $N \times N$ unit squares. Each snake occupies a sequence of at least two squares, and two consecutive squares of the sequence share a side. The first square of the sequence is the head. At most one snake sits on a square. A square that no snake occupies at the start is either empty or holds an obstacle.

In one step a snake first moves its head to an adjacent empty square, then pulls its tail, which empties one square. The initial direction of travel is given by the position of the head relative to the second square of the sequence. In every step a snake follows these rules:

• if it can move forward, meaning it hits no obstacle, no other snake and no part of itself and does not leave the board, it moves forward;
• if it cannot move forward, it tries to turn right;
• if that is impossible too, it tries to turn left;
• if that is impossible as well, it stays where it is and tries to move forward again in the next step.

Right and left are taken relative to the direction the snake currently faces. After a turn that direction becomes the new direction of travel. A snake that stays in place keeps its direction.

The square the head moves into must be empty at the moment of the decision. The tail is pulled only after the head has moved, so the square holding the tip of the tail is not yet empty, and the head cannot enter the square holding the tip of its own tail.

The snakes on the board are told apart by letters of the English alphabet. In every step all snakes move by the rules above, one after another in alphabetical order. A square freed by a snake that already moved in the same step is available to a snake that moves later. One step takes exactly one second. Write a program that, for the given starting layout, determines the layout after $T$ seconds.

The first line holds the integers $N$ and $T$, with $2 \le N \le 1000$ and $1 \le T \le 10^6$. $N$ is the side length of the board and $T$ is the time at which the layout of the snakes is wanted.

Each of the next $N$ lines holds $N$ characters. These lines describe the starting layout of the snakes, the empty squares and the obstacles. Each character is one of:

• . : the square is empty
• # : the square holds an obstacle
• an uppercase English letter : the square holds the head of a snake
• a lowercase English letter : the square holds a part of a snake other than the head

All squares marked with the same letter, uppercase or lowercase, form one snake. Every square of a snake is adjacent to exactly two other squares of that snake, except the head and the tip of the tail, which are adjacent to exactly one. No two different snakes carry the same letter.

Print $N$ lines of $N$ characters each. These lines must describe the layout after $T$ seconds, in the same format as the input.