408443: GYM103118 M Matrix Problem

A teacher gives his students a problem to test his students' construction skills.

The teacher has two $$$0 / 1$$$ matrices $$$A$$$ and $$$B$$$ with $$$n$$$ rows and $$$m$$$ columns, where all the $$$1$$$ of both matrices separately form a $$$4$$$-connected block. "Form one 4-connected block" means that starting at any $$$1$$$, you can reach all the $$$1$$$ by moving up, down, right or left, and you can not move into $$$0$$$.

Now the teacher gives a third matrix $$$C$$$ with $$$n$$$ rows and $$$m$$$ columns, and a specific position of this matrix is $$$1$$$ if and only if the corresponding positions of the two matrices are $$$1$$$.

You need to find two matrices $$$A$$$ and $$$B$$$ such that one of the positions of $$$C$$$ is $$$1$$$ if and only if the corresponding positions of $$$A, B$$$ are both $$$1$$$.

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(3 \le n, m \le 500)$$$ – the size of the matrices.

The next $$$n$$$ lines describe the matrix $$$C$$$. Each of the following $$$n$$$ lines contains $$$m$$$ characters $$$0$$$ or $$$1$$$.

It is guaranteed that the boundaries of the matrix $$$C$$$ are $$$0$$$, i.e., the $$$1$$$-st row, the $$$1$$$-st column, the $$$n$$$-th row and the $$$m$$$-th column of the matrix $$$C$$$ are $$$0$$$.

Print $$$2n$$$ lines and each line has $$$m$$$ characters $$$0$$$ or $$$1$$$.

The first $$$n$$$ lines describe the matrix $$$A$$$.

The next $$$n$$$ lines describe the matrix $$$B$$$.

If there are multiple answers, print any of them.

5 5
00000
00100
01010
01100
00000

11110
10100
11110
11100
11110
00001
01111
01011
01111
00001