B. LEGO-complete
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a binary matrix consisting of 0s and 1s. All the 1s form a single connected component under 4-directional connectivity (i.e., cells are connected if they share a side: up, down, left, or right).

Your task is to build a 2-layer LEGO structure exactly covering the region of 1s using the following three types of bricks:

  • 1×1 brick: covers exactly one cell.
  • 1×2 brick: covers two adjacent cells, and can be placed either horizontally or vertically.
  • L-shape brick: covers three cells forming an "L" shape — for example, a cell and its top and right neighbors. All four 90-degree rotations of this shape are allowed.

Your goal is to cover all the 1s using the specified types of bricks on both two layers while leaving all the 0s empty on both two layers. In addition, the entire LEGO structure must be structurally stable — that is, it Does Not Fall Apart.

We define two bricks to be adjacent if they are in different layer and share at least one common cell. A LEGO structure is said Does Not Fall Apart if all bricks form a single connected component through such adjacency.

If any solution exists, output any one of them. Otherwise, output -1.

Formally, you are given an $$$n \times m$$$ binary matrix $$$A$$$. You need to output two $$$n \times m$$$ matrices $$$B_0$$$ and $$$B_1$$$ representing the brick IDs on the upper and lower layers. Your output must satisfy the following:

  • Exact Coverage: If $$$A_{x, y} = 1$$$, then $$$B_{0,x,y}, B_{1,x,y} \in [1, 2nm]$$$. If $$$A_{x, y} = 0$$$, then $$$B_{0,x,y} = B_{1,x,y} = 0$$$.
  • Valid Bricks: Each brick ID appears only on one layer. Its occupied cells must form a valid shape: 1×1, 1×2, or L-shaped.
  • Does Not Fall Apart: Define two bricks $$$i$$$ and $$$j$$$ adjacent if there exists $$$(x, y)$$$ such that $$$\{B_{0,x,y}, B_{1,x,y}\} = \{i, j\}$$$. All bricks occur in $$$B$$$ must form a single connected component through such adjacency.
Input

The first line contains two integers $$$n, m$$$ $$$(1 \leq n, m \leq 1\times10^3 )$$$.

For the following $$$n$$$ lines, each line contains a 01 string with length $$$m$$$. Represents matrix $$$A$$$. It is guaranteed that all the 1s in $$$A$$$ under 4-directional connectivity.

Output

If any solution exists, output the two matrices $$$B_0$$$ and $$$B_1$$$ as follows: for each matrix, print $$$n$$$ lines, each line containing $$$m$$$ integers separated by spaces.

If no such solution exists, output -1.

Examples
Input
3 3
010
111
010
Output
0 3 0
4 1 1
0 1 0
0 2 0
2 2 5
0 6 0
Input
2 6
111111
010100
Output
1 1 2 2 5 5
0 1 0 2 0 0
6 3 3 4 4 7
0 8 0 9 0 0
Input
5 5
01001
11011
01110
11101
11111
Output
0 1 0 0 15
1 1 0 6 6
0 3 8 8 0
3 3 4 0 18
19 4 4 13 13
0 14 0 0 5
16 2 0 7 5
0 2 2 7 0
17 9 9 0 10
11 11 12 12 10
Note

The picture shows how examples are constructed.