숫자로 칠하기

오래전 '숫자로 칠하기(paint-by-numbers)'라는 취미가 있었다. 각 영역 안에 숫자가 적힌 선 그림을 받으면, 숫자마다 정해진 색으로 그 영역을 칠하는 방식이다. 예시는 아래와 같다.

여기서 풀어야 하는 문제는 이보다 조금 더 단순한 형태다.

$n \times m$ 크기의 격자 $(1 \le n, m \le 32)$가 주어지고, 모든 칸을 점(.) 또는 별(*) 중 하나로 "칠해야" 한다.

격자는 위에서 설명한 방식으로 직접 주어지지 않는다. 그러면 너무 쉬워지기 때문이다. 대신 각 행과 각 열에 대한 숫자 수열 $n + m$개가 주어지며, 이 정보만으로 어떤 칸이 점이고 어떤 칸이 별인지 알아내야 한다. 각 수열은 그 행 또는 열에서 연속된 별 덩어리의 길이를 순서대로 나열한 것이다. 서로 이웃한 두 별 덩어리 사이에는 점이 적어도 하나 있어야 한다.

예시는 아래와 같다(물고기 모양처럼 보이도록 만든 것이다).

이런 퍼즐 중에는 답이 하나로 정해지지 않는 경우도 있다. 모든 행과 열의 수열을 만족하는 격자가 여러 개라면, 그중 사전순으로 가장 작은 격자를 출력한다. 순서의 정의는 '출력' 항목에 자세히 나와 있다.

입력은 총 $n + m + 2$개의 줄로 이루어진다.

첫째 줄에는 행의 개수 $n$ $(1 \le n \le 32)$이, 둘째 줄에는 열의 개수 $m$ $(1 \le m \le 32)$이 주어진다.

다음 $n$개의 줄에는 각 행을 위에서 아래 순서로 설명하는 수열이 주어진다. 각 줄에는 그 행에 있는 별 덩어리들의 길이가 양의 정수로 공백을 사이에 두고 나열되며, 마지막에 $0$으로 끝난다. 별이 하나도 없는 행은 $0$ 하나로만 나타낸다.

그다음 $m$개의 줄에는 각 열을 왼쪽에서 오른쪽 순서로 같은 형식으로 설명하는 수열이 주어진다.

완성된 격자를 각 줄이 $m$개의 문자로 이루어진 $n$개의 줄로 출력한다. 각 문자는 점(.) 또는 별(*)이다.

모든 행과 열의 수열을 만족하는 격자가 여러 개라면 사전순으로 가장 작은 격자를 출력한다. 두 격자를 비교할 때는 칸을 행 우선 순서로, 즉 위쪽 행부터, 그리고 한 행 안에서는 왼쪽에서 오른쪽으로 읽으면서 처음으로 서로 달라지는 위치를 찾는다. 점(.)이 별(*)보다 작다고 볼 때, 그 위치에 점이 있는 격자가 더 작은 격자다. 그 격자를 출력한다.