네, 네, 노노그램입니다

노노그램(페인트 바이 넘버, 한지에라고도 한다)은 흑백 그림을 숫자 나열로 나타낸 논리 퍼즐이다. 숫자만 보고 원래 그림을 되살리는 것이 목표다. 퍼즐은 비어 있는 $n \times m$ 격자에서 시작하고, 각 행과 각 열에는 숫자 나열이 하나씩 붙는다. 숫자 나열은 그 줄에 있는 검은 칸 덩어리의 길이를 행에서는 왼쪽부터 오른쪽으로, 열에서는 위부터 아래로 적은 것이다. 어떤 행의 숫자가 4 5 1이면 그 행에는 검은 칸 4개짜리 덩어리가 있고, 그 뒤에 5개짜리 덩어리, 다시 그 뒤에 1개짜리 덩어리가 있다. 이웃한 두 덩어리 사이에는 흰 칸이 하나 이상 들어가고, 첫 덩어리 앞과 마지막 덩어리 뒤에는 흰 칸이 없어도 되고 여러 개 있어도 된다.

이 행의 길이가 13이면 들어맞는 배치는 정확히 네 가지다.

.XXXX.XXXXX.X
XXXX..XXXXX.X
XXXX.XXXXX..X
XXXX.XXXXX.X.

X는 검은 칸, .은 흰 칸이다.

네 배치 모두에서 검은 칸인 자리가 있다. 어느 배치가 정답이든 이 자리는 검은 칸이다.

?XXX??XXXX???

?는 어떤 배치에서는 검은 칸이고 다른 배치에서는 흰 칸인 자리다.

이것이 노노그램을 손으로 풀 때 쓰는 기본 기법이다. 한 줄에서 검은 칸을 채우면 그 칸을 지나는 줄의 배치가 제한되고, 그 줄에서 또 칸이 채워지며, 그 결과가 처음 줄을 다시 제한한다. 흰 칸도 같은 방식으로 나온다. 이미 확정된 칸과 들어맞는 모든 배치에서 흰 칸인 자리는 흰 칸이다. 많은 퍼즐은 이 추론을 되풀이하는 것만으로 풀린다. 더 어려운 퍼즐은 다른 방법이 필요하지만, 이 문제에서는 위 기법 외에는 아무것도 쓰지 않는다.

즉 어떤 칸은 그 칸이 속한 행의 숫자 나열이나 열의 숫자 나열이 같은 줄에서 이미 확정된 칸과 함께 색을 강제할 때에만 확정된다. 새로 확정되는 칸이 없을 때까지 행과 열을 훑으며 이 추론을 되풀이한다. 줄을 보는 순서를 바꿔도 최종 그림은 같다.

첫 줄에 격자의 행 개수 $n$과 열 개수 $m$이 주어진다 ($1 \le n, m \le 100$). 다음 $n$개 줄에는 맨 위 행부터 차례로 각 행의 숫자 나열이 $p\ v_1\ v_2\ \ldots\ v_p$ 꼴로 주어진다. $p$는 나열의 길이이고 $v_1 \ldots v_p$가 나열이다. 검은 칸이 하나도 없는 줄은 0 하나로 주어진다. 그 뒤 $m$개 줄에는 맨 왼쪽 열부터 차례로 각 열의 숫자 나열이 같은 꼴로 주어진다. 모든 숫자 나열과 들어맞는 흑백 배치가 적어도 하나 있다. 그 배치를 위 기법만으로 전부 되살릴 수 있는 경우도 있고 그렇지 않은 경우도 있다.

위 기법으로 얻을 수 있는 가장 완전한 그림을 $n$개 줄에 $m$개 문자씩 출력한다. 검은 칸은 X, 흰 칸은 ., 기법으로 색을 정할 수 없는 칸은 ?로 적는다.