Halma

Interview

Time limit1sMemory limit1024 MB

Summary

Given a grid of pieces, find every empty cell that the piece marked # can reach in one move, either by a single step or a chain of jumps, and mark those cells with +.

Level: Medium5 of 10
Topics: BFS, Graph, Simulation
Solved: No attempts yet

Statement

Halma is a traditional board game for two or four players, played on an $8 \times 8$ or $10 \times 10$ board. In December, when Santa Claus is busy, Mrs. Claus plays a one-player variant. To add variety, she uses different rectangular boards.

At the start, the player's pieces are in the starting area in one corner of the board. The goal is to move them to the finishing area in the opposite corner. There are two kinds of moves:

A step moves a piece to an empty neighboring cell in the same row or column. A step move covers only one cell.
A jump moves a piece over a neighboring piece to the empty cell directly behind it, in the same row or column. A piece can jump over only one piece at a time. Unlike in checkers, jumping over a piece does not affect that piece. A jump move can consist of one or more consecutive jumps made by the same piece. The sequence of jumps does not need to be maximal: the player can end the move at any moment, even if more jumps are possible.

Write a program that takes a board position and finds all cells to which the given piece can reach in one move.

Input

The first line contains the number of rows $N$ and the number of columns $M$ of the board ( $3 \le N, M \le 100$ ).

Each of the next $N$ lines contains exactly $M$ characters. A period '.' is an empty cell, a hash '#' is the piece under study, and an asterisk '*' is any other piece.

Output

Print exactly $N$ lines, each with exactly $M$ characters: the board from the input, where a plus '+' marks every cell that the piece under study can reach in one move.

Examples1

Example 1

Input

6 7
.......
.......
..*#*..
...*.*.
...*...
.......

Expected output

.......
...+...
.+*#*+.
...*.*.
...*.+.
.......