A. Alarm system (1000 points)

There are 3 large motorcycle gangs sharing the same parking lot. They have a lot of trouble with stolen bikes lately. You sense a great business opportunity here: you will try to sell them an alarm system to guard their bikes.

The parking lot is a rectangular grid, each cell is either empty or occupied (a bike is parking there). The alarm device you are selling will emit laser beams in the 4 cardinal directions (north/south/east/west) to measure distance to the nearest object. Whenever the measured distance changes, the system triggers loud sirens, blinking lamps and a hurd of gnus.

Due to safety regulations there cannot be anything immediately near a device so only one device can be installed in a cell. A device can be placed in any empty cell, however two devices using the same wave length cannot be placed with direct visibility between them (for example in the same row without an occupied cell between them), the system gets fooled and stops working.

   stolen motorcycle
source:
http://www.fugly.com/media/IMAGES/Whoops/stolen_motorcycle.jpg

Fortunately you have three different models of the device, each of them operating on different wave lengths, so you plan to recommend different models to the three gangs. The different models don't interfere in any way and they don't block each other's beam either.

Your goal is to sell as many devices as possible. To achieve this, you need to make a map of the most optimal placement where

Note that it is not a requirement that all bikes should be protected.

Input

The first line of the input is

W H
the size of the rectangular grid.

Then H lines follows, each contains W characters followed by a newline character.

The ith character of the jth line describes the ith cell of row j: '#' means occupied, ' ' means empty.

Output

The first line of the output is

W H N
the size of the rectangular grid as in the input and N the maximal number of devices which can be placed in the given parking lot.

Then H lines should follow describing an optimal placement of the devices: '#' means occupied cell, ' ' means empty cell, '1','2' and '3' means a device placed for the three groups respectively.

Example input

8 5
########
#     ##
## #   #
#     ##
########

Example output

8 5 10
########
#23 1 ##
##2#321#
#312  ##
########

Note: there may be multiple optimal device placements, any such solution is accepted.