21058번 - Language Survey 스페셜 저지다국어

In Gridnavia, three languages are spoken: Arwegian, Banish, and Cwedish. Gridnavia consists of an $n \times m$ grid, where at least one language is spoken in each cell. It is known that each of the three languages is spoken in a non-empty connected subset of grid cells. Connected means that it is possible to get between any pair of cells by moving through adjacent cells, where two cells are said to be adjacent if they share a side.

You have made a survey to find where in Gridnavia each language is spoken. The following question was sent to every cell in the region: "Please indicate if one or several of the languages is spoken in your cell". But due to a misprint, there were no choices after the question, so everyone just wrote "one" or "several". So the only thing you know is for each cell whether exactly one, or more than one language is spoken in that cell.

To make the best out of the situation, you should find any division of the three languages that corresponds to the information.

The first line of input contains two integers $n$ and $m$ ($1 \leq n,m \leq 200$).

The following $n$ lines each contain a string of length $m$, consisting of the characters 1 and 2. The $j$th character on the $i$th line is 1 if exactly one language is spoken in that cell, and 2 if at least two languages are spoken.

If the languages can be divided according to the information, then output three copies of the grid. The first copy should consist of characters "A" and ".", where the "A" indicates that Arwegian is spoken in that cell, and "." indicates that it isn't spoken. The following two grids should consist of characters "B" and ".", and "C" and ".", respectively, with the corresponding information about Banish and Cwedish.

Remember that the three regions have to be connected and non-empty, and every cell must be part of some region. For readability, it is recommended to put empty lines in between the three grids, but it is not necessary to do so. If there are multiple solutions any one will be accepted.

Otherwise, if there is no way to divide the languages, output "impossible".