Game map

Vasya still likes to play computer games, and he is still employed as a game tester. He has given up on doing anything remotely interesting at work. To put his creative potential to use, he is cooperating with his colleagues Petya and Kolya on a hobby project. Petya has told Vasya that there are many great indie games out there, and that even a small team can do well in that business. He is not being entirely honest. He has not said what percentage of those indie games gains any popularity, or how many of those projects are completed at all.

The new game will be in the popular roguelike genre. The bearded Kolya keeps correcting Vasya: it is roguelite or roguelikelike. One of the most important components of a roguelike is the randomly generated gameworld. A new adventure at each launch is what makes the "Losing is fun" motto work. The friends are now working on world map generation for their game.

The game takes place in caves. The world map is a rectangular field of cells. Each cell is either traversable, containing a level that the player must pass, or non-traversable and empty. The player begins at the top left corner cell, which must be traversable. After finishing a level, the player can move down or right to an adjacent cell, if that cell is traversable. While in the last row or column of the field, the player can leave the field. This ends the game, and the player wins.

For balance, Petya has placed two more limitations on the map:

1. The player can reach each traversable cell from the starting cell by only one path.
2. The player can finish the game starting from any traversable cell, although there can be several ways to do that.

Kolya is the chief programmer of the game and he will write the generation code. He noticed that a randomly generated field almost never satisfies these criteria. For this reason, he randomly generates only some of the field cells and leaves the rest in an <<indefinite>> state. Next he must run an algorithm that fills in the remaining cells so that the resulting map satisfies all the conditions. To increase the amount of content in the game, the algorithm must maximize the number of traversable cells.

The trouble is, Kolya is not a big expert on algorithmic programming and cannot implement the last step on his own. Help the friends make their dream come true!

The first line contains two integers defining the size of the game field: $H$, the number of rows, and $W$, the number of columns ($1 \le H, W \le 18$).

It is followed by the field contents as $H$ lines with $W$ symbols in each. Traversable cells are marked by the period '.', non-traversable cells by the letter 'X', and indefinite cells by the question mark '?'.

If the field cannot be defined in a correct state, print the number $-1$.

Otherwise, print on the first line an integer $K$, the number of traversable cells in the defined field. This number must be as large as possible. Then print the defined field in the same format as the input, without question marks.

If there are several optimal solutions, print any of them.