Bar Code

Bar Code is a puzzle invented by Thinh Van Duc Lai in 2017. The New York Times first published it.

The puzzle is played on a square grid of $n \times n$ unit squares, which has $(n+1) \times (n+1)$ grid points. For a given specification, mark some of the borders of the unit squares by drawing a vertical or horizontal bar. The markings must satisfy these conditions:

• For each row and column, the specification gives how many separate groups of consecutive bars of the same orientation there must be. For example, the specification 2 1 1 requires 3 groups of 2, 1, and 1 bars, with at least one unmarked border between groups.
• No 2 bars may touch.

For example, here is a $n = 6$ puzzle with $7$ borders in each row. The following markings meet this specification:

1101010
1101001
1100101
0110101

Here 1 denotes a bar and 0 denotes an unmarked border.

The illustration shows the solution for sample input 3.

The first line contains an integer $n$ ($0 < n \le 9$). The next $n$ lines describe the vertical bars. Line $i$ lists the group sizes for row $i$, counting from the top. Each line has one or more non-negative integers. If a line is the single integer 0, no borders may be marked in that row. Otherwise, none of the integers on the line is 0.

The following $n$ lines describe the horizontal bars. Line $j$ lists the group sizes for column $j$, counting from the left, in the same format.

Print $n$ strings of length $n+1$ for the vertical borders. The $j$-th character of the $i$-th string is 1 if the $j$-th vertical border in row $i$ is a bar, and 0 otherwise.

Then print $n+1$ strings of length $n$ for the horizontal borders. The $j$-th character of the $i$-th string is 1 if the $i$-th horizontal border in column $j$ is a bar, and 0 otherwise.

Rows are counted from top to bottom, and columns from left to right. If several solutions exist, you may print any of them. You may assume that at least one valid marking exists.