Screamers in the Storm

As you might remember from your first years in school, the human race invented beer brewing at least about 7000 years ago. The total amount of beer consumed since then must be monumental, and the rate of consumption is surely not going to shrink in the coming millennia.

To celebrate these facts, we invite you to implement a game that seems unrelated to beer brewing. It is quite possible, however, that after a successful implementation you might feel a little dizzy, just as if you have had a little more than your daily dose of beer.

The game is played on a rectangular M × N grid of square tiles of different types.

Animals and food

There are some number of animals on the grid, and each animal occupies exactly one tile.

Grass grows, sheep eat grass, wolves eat sheep, and both wolves and sheep can die of starvation.

Turns and animal actions

Each turn consists of actions in the following order:

1. All animals on the grid move. Each wolf moves to a neighbouring tile to the east (right). If the wolf's move is not possible, the wolf moves to the westernmost tile in its row. Each sheep moves to a neighbouring tile to the south (down). If the sheep's move is not possible, the sheep moves to the northernmost tile in its column.
2. If a wolf and a sheep occupy the same tile, the wolf eats the sheep and the tile becomes a Soil with carcass tile.
3. If a sheep is on a Soil with grass tile, the sheep eats the grass and the tile becomes a Soil tile.
4. If a wolf hasn't eaten in any of the last 10 turns including the current turn, it dies and the tile becomes a Soil with carcass tile.
5. If a sheep hasn't eaten in any of the last 5 turns including the current turn, it dies and the tile becomes a Soil with carcass tile.

Types of tiles and their changes

There are three types of tiles. The type of a tile may change in the course of the game.

1. Soil tile: 3 turns after the beginning of the game, or 3 turns after the tile became a Soil tile, the tile becomes a Soil with grass tile.
2. Soil with grass tile: If the grass is eaten by a sheep, the tile immediately becomes a Soil tile. The grass grows again at the tile after 3 turns.
3. Soil with carcass tile: Whenever an animal dies on a tile of any type, the tile immediately becomes a Soil with carcass tile. Animals can still move to this tile, but grass will never grow on this tile again. As the game progresses, more carcasses may accumulate on the tile.

The first line of the input contains three integers T, N and M (1 ≤ T ≤ 100, 1 ≤ M, N ≤ 20), where T is the number of turns, M is the number of rows and N is the number of columns of the grid. The following M lines contain N characters each. The characters denote the types of tiles:

• . (dot character) denotes a Soil tile
• S denotes a Soil tile with a sheep on it
• W denotes a Soil tile with a wolf on it

Output M lines each containing N characters describing the state of the grid after the end of the T-th turn. If there is an animal on a tile, output:

• W for a tile with a wolf on it
• S for a tile with a sheep on it

Otherwise, output:

• * for a Soil with carcass tile
• # for a Soil with grass tile
• . (dot character) for a Soil tile