Guess the Pattern

Given a 01 string, you can group consecutive 1’s into blocks and write down their lengths. This is called the ‘block length sequence (BLS)’ for that string. For example, the BLS for 011100110100011 is 3, 2, 1, 2.

Similarly, given a 01 matrix, you can write down the BLS for each row and each column. Given these BLS’s, your task is to restore the 01 matrix.

Rows are read from left to right, while columns are read from top to bottom. Each test case is guaranteed to be solvable, and you’re free to output any (but only one!) solution you like.

The input contains at most 10 test cases. Each test case begins with two integers n and m (1 <= n, m <= 15), the number of rows and the number of columns. The next n lines contain the BLS’s for each row, from top to bottom, and the next m lines contains the BLS’s for each column, from left to right. Each BLS ends with zero. The input ends with n = m = 0.

For each case, print exactly one feasible solution you find. Each row of the matrix should occupy exactly one line. There shouldn’t be any spaces within the matrix, nor there can be any empty lines between rows, but do print an empty after each test case.

4 4
2 1 0
3 0
3 0
1 1 0
4 0
3 0
3 0
1 0
0 0

**.*
***.
***.
*.*.

2009 “NIT Cup” National Invitational Contest