Island

A tube flying his private plane over the middle of the Pacific Ocean ran out of fuel and made an emergency landing in the middle of a remote island. Luckily, the tube found a $N \times M$ grid map that contains all the information about the area near the island.

Each cell of the grid is either sea or land. All cells on the outermost border are sea. A cell is written as $(x, y)$ ($1 \le x \le N$, $1 \le y \le M$), and any cell with $x = 1$, $x = N$, $y = 1$, or $y = M$ is guaranteed to be sea. Every land cell is part of some island. Two land cells that share an edge belong to the same island. In other words, if $(x, y)$ and $(x+1, y)$ are both land, they belong to the same island, and if $(x, y)$ and $(x, y+1)$ are both land, they also belong to the same island.

The tube picked up a raft at its current position and plans to use it to cross the open ocean in search of fuel. The tube can move from any cell to one of its four adjacent cells. Whether the destination is land or sea does not matter, because the tube has a raft. The tube's goal is to move from its current position, reach the open sea, find fuel, and come back.

The tube faces two problems. First, one of the islands in the area is home to dangerous hunters who want to catch and eat ducks. The island the tube is on is known to be safe, but if escaping requires passing through the hunters' island, the tube is in serious danger. Second, the tube does not know which island on the map it is on. The island it is on might border the outermost sea directly, or it might be surrounded by other islands in layers.

The tube wants to know whether each island on the map is safe or dangerous. An island $S$ is dangerous if there is another island $T$ that must be passed through to reach an outermost cell from $S$. An island $S$ is safe if it is not dangerous. Help the tube find which islands are safe and which are dangerous.

The first line contains two integers $N$ and $M$ separated by a space. ($3 \le N, M \le 2{,}000$)

The next $N$ lines each contain a string of length $M$. The $j$-th character of the $i$-th line is # if cell $(i, j)$ is land and . if it is sea. No other characters appear. The grid contains at least one land cell.

Print $N$ lines, each containing a string of length $M$. The $j$-th character of the $i$-th line describes cell $(i, j)$. Print . for sea, O for a cell of a safe island, and X for a cell of a dangerous island.