Bar Code

Bar Code는 Thinh Van Duc Lai가 2017년에 고안한 퍼즐이다. 뉴욕 타임스에 처음 실렸다.

이 퍼즐은 $n \times n$ 개의 단위 정사각형으로 이루어진, $(n+1) \times (n+1)$ 개의 격자점을 가진 정사각형 격자 위에서 진행한다. 주어진 명세에 맞게 단위 정사각형의 테두리 일부에 세로 또는 가로 막대를 그려 표시한다. 표시는 다음 조건을 만족해야 한다.

• 각 행과 열마다 명세에는 같은 방향으로 연속된 막대 묶음이 몇 개 있어야 하는지가 적혀 있다. 예를 들어 명세가 2 1 1이면 2개, 1개, 1개짜리 묶음이 3개 있어야 하며, 묶음 사이에는 표시되지 않은 테두리가 최소 하나 있어야 한다.
• 막대 2개가 서로 닿으면 안 된다.

예를 들어 각 행에 테두리가 $7$개 있는 $n = 6$ 퍼즐에서 다음 표시는 명세를 만족한다.

1101010
1101001
1100101
0110101

여기서 1은 막대가 있는 테두리, 0은 표시되지 않은 테두리를 뜻한다.

그림은 입력 3의 해를 보여 준다.

첫 줄에 정수 $n$ ($0 < n \le 9$)이 주어진다. 이어지는 $n$개의 줄은 세로 막대의 묶음 크기를 나타낸다. $i$번째 줄에는 위에서 $i$번째 행의 묶음 크기가 1개 이상의 음이 아닌 정수로 주어진다. 줄에 정수 0 하나만 있으면 그 행에는 테두리를 표시할 수 없다. 그렇지 않으면 줄의 정수는 모두 0이 아니다.

그 다음 $n$개의 줄은 가로 막대의 묶음 크기를 나타낸다. $j$번째 줄에는 왼쪽에서 $j$번째 열의 묶음 크기가 같은 형식으로 주어진다.

길이 $n+1$인 문자열을 $n$개 출력한다. $i$번째 문자열의 $j$번째 문자가 1이면 $i$번째 행의 $j$번째 세로 테두리에 막대가 있다는 뜻이다.

이어서 길이 $n$인 문자열을 $n+1$개 출력한다. $i$번째 문자열의 $j$번째 문자가 1이면 $j$번째 열의 $i$번째 가로 테두리에 막대가 있다는 뜻이다.

행은 위에서 아래로, 열은 왼쪽에서 오른쪽으로 센다. 해가 여럿이면 아무것이나 출력해도 된다. 명세를 만족하는 표시가 하나 이상 존재한다고 가정해도 된다.