30607번 - Loops 스페셜 저지다국어

문제

Consider four integers $A,ドル $B,ドル $C,ドル and $D,ドル such that $A < B < C < D$. Let's put them in the corners of a square in some order and draw a loop $A - B - C - D - A$. Depending on the arrangement of the integers, we can get different loop shapes, but some arrangements produce the same shape:

There are three possible loop shapes we can get:

Now consider an $n\times m$ matrix filled with distinct integers from 1ドル$ to $nm,ドル inclusive. Each 2ドル\times 2$ square in this matrix can be seen as a square with integers in its corners. Let's build a loop for each of these squares like we did before:

Your task is to perform the inverse operation. You are given the shape types for all $(n-1)(m-1)$ loops, and you need to build an $n\times m$ matrix filled with distinct integers from 1ドル$ to $nm,ドル inclusive, that produces these shapes.

입력

The first line contains two integers $n$ and $m$ (2ドル\le n, m\le 500$).

Each of the next $n-1$ lines contains a string of $m-1$ characters without spaces. Each character is a digit from 1ドル$ to 3ドル,ドル denoting the type of the shape of the corresponding loop.

출력

Print an $n\times m$ matrix filled with distinct integers from 1ドル$ to $nm,ドル inclusive, that produces the shapes of the loops in the input.

It can be shown that such a matrix always exists. If there are multiple answers, print any of them.

제한

힌트