K. Trapping Rain Water
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
How hard can a LeetCode problem be?
— Some poor soul
Tired of the long and complex problem statements of ICPC contests, Samarth has decided to go back to practicing LeetCode. As a LeetCode Guardian, he's able to solve most LeetCode problems and doesn't find them difficult at all, especially since the problem statements tend to be short. He opened up the classic LeetCode problem, Trapping Rain Water. In this problem, you are given a 2D structure and have to compute where water is trapped in it after it rains from above. The 2D structure is given as an elevation map where each column has a certain height (see Sample 1 for a clear example).

However, Samarth is rusty when it comes to reading. He's never been particularly good at it and always had an ICPC teammate read problems for him. So when Samarth read the one sentence problem statement in Trapping Rain Water, he did not realize that the 2D structure is an elevation map. Instead, Samarth has the following assumptions about the 2D structure:

  • The 2D structure is given as a grid of cells denoted by 'x' and '.', where '.' represents an empty cell and 'x' represents a block in a cell.
  • The bottom row of the 2D structure is a fully occupied row of blocks.

Samarth also has the following assumptions about how water works:

  • Water can only flow through empty cells (specifically, it can't flow through the space between adjacent blocks or between diagonally adjacent blocks).
  • Water doesn't stick to blocks; if water runs down the side of a block, it won't stick to the bottom of the block.
  • Water doesn't spread while falling. It falls straight downward due to gravity.
  • Water that exits the grid will never enter the grid again.
  • Air bubbles will not form when water flows into a trapped space.
  • It rains for an arbitrarily long amount of time, and then the water will drain for an arbitrarily long amount of time.
  • The siphon effect does not apply.

Help Samarth determine which cells will trap rain water. After all, how hard can a LeetCode problem be?

Input

The first line of input consists of two integers $$$n$$$ and $$$m$$$ $$$(3 \le n,m \le 10^6, n\cdot m \le 10^6)$$$ — the dimensions of the grid.

The following $$$n$$$ lines of input each contain a row of the grid, represented as a string of $$$m$$$ characters which are either '.' or 'x'.

It is guaranteed that the last row of the grid only has 'x'.

Output

Output the grid after it has rained. Specifically, output $$$n$$$ lines of $$$m$$$ characters each. Each character in the grid should be 'x' (block), '.' (empty cell), or '$$$\texttt{\textasciitilde}$$$' (filled with water).

Examples
Input
5 12
............
.......x....
...x...xx.x.
.x.xx.xxxxxx
xxxxxxxxxxxx
Output
............
.......x....
...x~~~xx~x.
.x~xx~xxxxxx
xxxxxxxxxxxx
Input
7 5
.....
x...x
x...x
xx.xx
x.x.x
x...x
xxxxx
Output
.....
x~~~x
x~~~x
xx~xx
x.x.x
x...x
xxxxx
Input
8 7
xxx.xxx
.......
.xx.x..
...xx..
.......
xx.x...
x..x..x
xxxxxxx
Output
xxx.xxx
.......
.xx~x..
...xx..
.......
xx~x...
x~~x~~x
xxxxxxx
Input
7 7
xxx.xxx
.......
.......
x.xxx..
x.x.x.x
x.....x
xxxxxxx
Output
xxx.xxx
.......
.......
x.xxx..
x~x~x~x
x~~~~~x
xxxxxxx
Input
5 7
xxxxx.x
....x..
x.x.x.x
x.x...x
xxxxxxx
Output
xxxxx.x
....x..
x~x~x~x
x~x~~~x
xxxxxxx