시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

You have a rectangular board consisting of n × m squares. Each square contains a character which is either “*”, “+”, or “.”.

A tromino is a figure formed by a square of the board, called the center, and two other squares, each sharing an edge with the center. A tromino is L-shaped if these two squares have a common vertex, and I-shaped otherwise.

You can draw some disjoint trominoes on the board. The center of an I-shaped tromino must contain “+”. The center of an L-shaped tromino must contain either “*” or “+”. All non-center squares of all trominoes must contain “.”.

Your goal is to draw the maximum number of non-intersecting polyominoes.

입력

The first line contains two integers n and m: the number of rows and columns of the board (2 ≤ n, m ≤ 100).

Each of the next n lines contains m characters, and each character is either “*”, “+”, or “.”. Together, these lines describe the board.

출력

Print n lines, each containing m characters: the board with trominoes on it. If a square belongs to some tromino, output a lowercase English letter, and if not, output the character contained in this square. Squares of the same tromino must contain the same letter. Squares which share an edge and belong to different trominoes must contain different letters.

If there are several possible answers, print any one of them.

예제 입력 1

2 2
*.
..

예제 출력 1

aa
a.

예제 입력 2

3 3
...
.*.
...

예제 출력 2

.a.
aa.
...

예제 입력 3

5 5
+*..+
..++.
.+.++
.**.+
.+*.+

예제 출력 3

+*baa
.bb+a
ccc++
.**.+
.+*.+

예제 입력 4

11 13
.............
.+++....+++..
....+..+.....
....+..+.....
....+..+.....
.+++....+++..
....+......+.
....+......+.
....+......+.
.+++....+++..
.............

예제 출력 4

.abc....abc..
aabcc..aabcc.
..baaacccb...
...dddeee....
.abfffgggbc..
aab+a..aabcc.
..baa...abaaa
...ccc....ddd
.abddd..abccc
aabee..aabee.
..be.....be..