Painting a board P40479

Write a program to paint several zones of an n × m board. Here, a zone is defined as a maximal set of adjoining cells, both horizontally and vertically.

Input

Input consists of several cases. Every case begins with the dimensions n and m, followed by n lines with m characters each. A character ‘#’ indicates a wall. A dot indicates an empty cell. A lowercase or uppercase letter indicates what must be used to fill that zone. Every zone has at most one letter. Suppose 3 ≤ n ≤ 30, 3 ≤ m ≤ 30, and that the borders of the board only have walls.

Output

For every case, print the result of painting the board, followed by an empty line.