Problem E. Terrarium

Author:A. Klenin, T. Chistyakov   Time limit:3 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

A zoology research lab has a terrarium with rare species of snakes. Terrarium is a flat box filled with soil, and has a glass top allowing to watch the snakes. There are trenches in the soil, and snakes constantly move along the trenches. All snakes have diameter of 1 cm and integer length of no less than 2 cm.

While watching the snakes, the zoologists discovered a pattern in their movement: each snake moves at a speed of 1 cm per second forward, until it encounters either a wall or another snake. Faced an obstacle, snake first tries to turn right, if there is also obstacle on the right, then it tries to turn left. If there is obstacle on the left also, the snake waits for a second before trying to move again.

In order to validate the discovery, it was decided to write a program that simulates snakes' behaviour. This task was assigned to you.

The terrarium is represented by an array of N × N characters. Each character is one of:

Snakes are represented by latin letters, so there are no more than 26 snakes in terrarium. Snakes try to move in alphabetical order every second.

Your program must output the state of the terrarium after T seconds.

Input file format

First line of input file contains integers N T. Following N lines contain N characters each — the initial state of the terrarium. The input file guarantees unambiguous recognition of snakes — all snakes are continuous, every character of snake's body has exactly two neighbour characters belonging to the same snake, while head and tip of the tail have exactly one.

Output file format

Output file must contain N lines of N characters — the state of the terrarium after T seconds.

Constraints

2 ≤ N ≤ 1000, 1 ≤ T ≤ 106.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 8
.bB.
....
a.#.
aaA.
.baa
.BAa
..#.
....
2
7 100000
aA.....
a#####D
aa....d
......d
......d
......d
.......
aaaaADd
.#####d
......d
......d
.......
.......
.......

0.073s 0.007s 15