Nonograms P16479

Nonogram is a solitaire game played on a n × n grid, where each cell has to be painted either black or white. Every row (and column) has a list of integer numbers, which correspond to the lengths of the runs of black squares in that row (or column), in order.

For instance, this is an example of solved nonogram:

Please write a program to solve nonograms.

Input

Input consists of several cases. Every case begins with a line with n, followed by n lines with the numbers of the i-th row, followed by n lines with the numbers of the j-th column. Assume 1 ≤ n ≤ 15. Every given nonogram has exactly one solution.

Output

For every case, print its number, followed by the solution of the nonogram, followed by a blank line.