G. Make Everything White
time limit per test
1 second
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Consider a rectangular grid of size $$$N \times M$$$. Each cell is colored black or white.

For each cell, you have to execute exactly one of the three operations given below.

  1. Do not change anything.
  2. Change the color of all neighbor cells (black to white, white to black).
  3. Change the color of all neighbor cells and itself.

Two cells are neighbors if they share a side.

Your goal is make all cells white. Find a way to achieve it, or determine that it is impossible.

Input

The first line contains two integers $$$N$$$ and $$$M$$$, the dimensions of the grid ($$$1 \le N, M \le 2000$$$).

Each of the next $$$N$$$ lines describes one row of the grid. Each of these lines contains $$$M$$$ characters denoting the colors of cells in the row. Each character is either "B" for black or "W" for white.

Output

Print "-1" on the first line if it is impossible to make all cells white.

Otherwise, print "1" on the first line, followed by $$$N$$$ more lines. Each of these lines must contain $$$M$$$ characters which describe the operations you chose for the respective row of the grid. Each of the characters must be either "1", "2", or "3", corresponding to the three operations in the statement. If there are several solutions, print any one of them.

Examples
Input
2 3
WBW
BWB
Output
1
111
121
Input
1 1
B
Output
1
3