SimRoad 3

JOI sells a simulation game called SimRoad. In this game, the player becomes the ruler of the country where the game takes place and performs various operations to make the country prosper.

The country is in a primitive age. Settlements are scattered across the country, but much of the country is covered with tall grass, so residents cannot easily move between settlements in that state. Your first mission as the player is to mow the grass so that residents can move easily between settlements.

The state of the country is represented by cells divided into $W$ cells in the east-west direction and $H$ cells in the north-south direction, each in one of three states. 'w' means the cell is covered with grass, '.' means the cell is clear ground (not covered with grass), and '@' means there is a settlement in the cell.

Residents can move freely to adjacent cells in the four directions, north, south, east, and west, if the cell is a settlement or clear ground, but they cannot move into a cell covered with grass. Therefore, to let residents move easily between settlements, you must mow the grass on grass-covered cells to turn them into clear ground so that every settlement can reach every other settlement.

Mowing the grass on a grass-covered cell turns it into clear ground, but mowing requires putting residents to work, and mowing one cell costs 1 dollar. Considering future prosperity, spending less money is better.

Naturally, there can be many ways to mow the grass. From the given state of the country, mow in a way that mows as few cells as possible, and produce the resulting state of the country.

Basic algorithm (BASIC ALGORITHM): Let $y'$ be $H/2$ if $H$ is even, and $(H + 1)/2$ if $H$ is odd. First, mow all grass-covered cells in the $y'$-th row from the north. Next, for every settlement, if there are grass-covered cells between that settlement and the $y'$-th cell from the north in the north-south direction, mow all of them.

The input file is given in the following format.

• The first line contains integers $W$ and $H$ separated by a space.
• The following $H$ lines each contain a string of $W$ characters and represent the state of the country. In the $y$-th of these lines, the $x$-th character is 'w', '.', or '@', and it represents the state of the cell at the $y$-th position from the north and the $x$-th position from the west.

Submit the output data as a file.

• Write the state of the country after mowing. The output consists of $H$ lines, each a string of $W$ characters. In the $y$-th line, the $x$-th character must be 'w', '.', or '@', representing the state of the cell at the $y$-th position from the north and the $x$-th position from the west.

• $1 \le W \le 100$: the number of cells in the east-west direction
• $1 \le H \le 100$: the number of cells in the north-south direction

In this output example, 7 grass-covered cells were mowed and turned into clear ground, so it costs 7 dollars. If this output example is submitted, you get 20 points if no one submits an output of a country state that can be made for less money than yours; but if Em is 6 dollars, you get 12.9 points.

The output of the basic algorithm for the sample input is as follows. It mows 10 grass-covered cells and turns them into clear ground, so it costs 10 dollars.

w@ww@w@
w.ww.w.
....@..
@w.w.ww
ww@.@w.