C. And again the maze
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The level map of a certain game is a rectangular maze with the size of $$$N \times M$$$ cells. The player needs to move from the top-left cell to the bottom-right cell. In one move, the player can step to a side-adjacent cell, if there is no obstacle in it.

After reviewing the game results, the game designer determined that the shortest path from the top-left to the bottom-right cell was too short. Therefore, he wants to place an additional obstacle in one of the free cells so that the shortest path becomes longer, but still exists. Find all possible ways to do this.

Input

The first line contains two numbers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 1000$$$).

Next there are $$$N$$$ lines of $$$M$$$ characters each, representing the cells of the maze: the symbol '.' indicates an empty cell, and the 'X' symbol shows an occupied cell.

It is guaranteed that the top-left and bottom-right cells are free and there is a path between them.

Output

Print the maze map (you do not need to print the dimensions), marking with the symbol '*' those cells in which you can put an additional obstacle.

Example
Input
4 5
.....
.XX..
.X...
...X.
Output
.***.
.XX..
.X...
...X.