Each cell in an $N \times M$ grid is colored either white or black. For each cell, you can perform one of the following three actions:

1. Do nothing.
2. Invert the colors of all cells adjacent to the selected cell (the selected cell itself is not inverted).
3. Invert the colors of the selected cell and all cells adjacent to it.

You want to make all cells white. Find a way to make all cells white.

Input

The first line contains $N$ and $M$ ($1 \le N, M \le 2000$). The following $N$ lines each contain a string of length $M$. The strings consist of 'B' and 'W', representing black and white cells, respectively.

Output

If it is impossible to make all cells white, output -1 on the first line. If it is possible, output 1 on the first line, and then output $N$ lines, each containing $M$ numbers without spaces. The $j$-th number in the $i$-th line represents the action taken on the cell at the $i$-th row and $j$-th column. 1 means doing nothing, 2 means inverting all adjacent cells, and 3 means inverting the cell itself and all adjacent cells.

Examples

Input 1

2 3
WBW
BWB

Output 1

1
111
121

Input 2

1 1
B

Output 2

1
3