Global Warming

Interview

Time limit1sMemory limit128 MB

Summary

Given a small land/sea grid, mark every land cell with three or more sea neighbours as sea simultaneously, then print the tight bounding box of the remaining land.

Level: Easy3 of 10
Topics: Array, Simulation, Implementation, Matrix
Solved: No attempts yet

Problem

The map of an archipelago can be represented as an $R \times C$ grid. Each cell is either land (X) or sea (.).

As global warming raises the sea level, after 50 years every land cell that has sea on three or more of its four orthogonally adjacent cells sinks under water. Every cell outside the grid is treated as sea. All cells are judged simultaneously against the current map (one cell sinking does not affect its neighbours within the same step).

You want to draw the map after 50 years. Print only the smallest rectangle that contains every remaining piece of land. At least one land cell always remains after 50 years.

Input

The first line contains the number of rows $R$ and the number of columns $C$ ( $1 \le R, C \le 10$ ).

Each of the next $R$ lines contains $C$ characters describing the current map, where X is land and . is sea.

Output

Print the map after 50 years. Output only the smallest rectangle that contains all remaining land; do not print anything outside it.

Examples2

Example 1
Input
```
5 3
...
.X.
.X.
.X.
...
```
Expected output
```
X
```

Example 2

Input

3 10
..........
..XXX.XXX.
XXX.......

Expected output

.XX...X
XX.....