Terrarium

A zoology research lab keeps a terrarium of rare snakes. The terrarium is a flat, soil-filled box with a glass top, so the snakes can be observed from above. Trenches run through the soil, and the snakes constantly crawl along them. Every snake is $1$ cm in diameter and has an integer length of at least $2$ cm.

The zoologists found a movement pattern. Once per second a snake tries to move $1$ cm straight forward, in the direction its head is facing. If an obstacle (a wall or a snake) is directly ahead, it first tries to turn right; if the cell to its right is also blocked, it tries to turn left; if the cell to its left is blocked as well, the snake stays put for that second. Here right and left are taken from the snake's own point of view, relative to the direction it faces. A single move (straight or after a turn) advances the head by one cell and pulls every body segment one cell forward along the snake's own track, so the tail vacates its former cell.

The terrarium is an $N \times N$ grid of characters. Each cell is one of:

• . — a trench (empty and walkable)
• # — a wall
• A–Z — the head of a snake
• a–z — a body segment or the tail tip of a snake

Each snake is labelled by a single latin letter, so there are at most $26$ snakes: its head is the uppercase letter and its body uses the matching lowercase letter. A snake faces the direction that points from its first body segment toward its head.

Every second the snakes attempt to move one at a time, in alphabetical order (A, then B, and so on). Each snake acts on the board as left by the snakes that already moved during the same second. Output the state of the terrarium after exactly $T$ seconds.

The first line contains two integers $N$ and $T$. Each of the next $N$ lines contains $N$ characters describing the initial state of the terrarium.

The input is guaranteed to identify the snakes unambiguously: every snake is a single connected chain, each interior body segment has exactly two neighbours belonging to the same snake, and the head and the tail tip each have exactly one such neighbour.

Output $N$ lines of $N$ characters each — the state of the terrarium after $T$ seconds, using the same character convention as the input.

• $2 \le N \le 1000$
• $1 \le T \le 10^6$