Paint by Numbers

Long ago there was a craft known as paint-by-numbers: you were handed a line drawing with a number written inside each enclosed region, and each number told you which colour to use for that region. An example is shown below.

The puzzle you have to solve here is more linear, in a sense.

You are given an $n \times m$ grid $(1 \le n, m \le 32)$ that you must "colour" so that every cell holds either a dot (.) or a star (*).

The grid is not described in the usual paint-by-numbers way — that would be too easy. Instead, you must deduce which cells are dots and which are stars from a set of $n + m$ number sequences: one sequence for every row and one for every column. Each sequence gives, in order, the length of every run of consecutive stars in that row or column. Two consecutive runs of stars must be separated by at least one dot.

An example is shown below (it is meant to look like a fish).

Some of these puzzles have more than one valid grid. When several grids satisfy all of the row and column sequences, output the lexicographically smallest one; the ordering is defined precisely in the Output section.

The input consists of $n + m + 2$ lines.

The first line contains the integer $n$ $(1 \le n \le 32)$, the number of rows. The second line contains the integer $m$ $(1 \le m \le 32)$, the number of columns.

The next $n$ lines describe the rows from top to bottom. Each line lists the lengths of the star runs in that row as space-separated positive integers and is terminated by a $0$. A row that contains no stars is written as a single $0$.

The following $m$ lines describe the columns from left to right, in the same format.

Print the finished grid as $n$ lines of $m$ characters each, where every character is a dot (.) or a star (*).

When more than one grid satisfies every row and column sequence, print the lexicographically smallest one. To compare two grids, read their cells in row-major order — the top row first, and left to right within each row — and find the first position where the two grids differ. Treating a dot (.) as smaller than a star (*), the grid that has a dot at that position is the smaller one. Print that grid.