eolymp
bolt
Try our new interface for solving problems
Problems

Puzzle

Puzzle

Time limit 1 second
Memory limit 128 MiB

You've decided to make a puzzle as a part of the "re-branding" campaign run by your company. In the box this puzzle will look as the new logo of your company, that is, it will be a set of 9 (nine) connected unit squares on a rectangular grid. However, these 9 squares will not necessarily all be glued together, i.e., they may form several connected parts (however, you're not allowed to split squares in the middle). The objective of the puzzle will be to rearrange those parts so that they form a 3 * 3 square. When rearranging, one is only allowed to shift parts, and NOT to rotate or to flip them.

To make the puzzle more challenging, you need to have as few parts as possible. Given the logo, compute how many parts do you need and how to rearrange them into a 3 * 3 square.

Every word "connected" in the problem statement means connectedness in the side-by-side sense.

Input data

The first line contains two integers h and w. The next h lines will contain w characters each, describing your logo. Each of those characters will be either '.' (dot), denoting an empty square, or X (capital English letter X), denoting a square occupied by the logo. All the X's will form a connected figure, there will be exactly 9 X's in the input. The first line, the last line, the first column and the last column will contain at least one X, in other words, there will not be unnecessary empty rows at any side of the grid.

Output data

On the first line, output the required number of parts k. Afterwards, output one of the possible rearrangements, more precisely: on the next h lines output the logo with all the X's replaced by the first k capital letters of English alphabet, each letter denoting one part. Then output an empty line, and then 3 lines containing 3 characters each, containing the same k parts but shifted around so that they form a 3 * 3 square.

All the parts must be connected, and k must be as little as possible. If there're several possible solutions, output any.

Examples

Input example #1
4 5
....X
....X
..XXX
XXXX.
Output example #1
3
....A
....C
..CCC
BBCC.

BBC
CCC
CCA
Source 2007 Петрозаводск, Petr Mitrichev Contest 2, Январь 30, Задача I