Yes, Yes, It's Nonograms

Time limit2sMemory limit512 MB

Summary
Repeatedly apply line-by-line nonogram deduction until no square's color is forced, then print the resulting grid.
Level

Medium7 of 10

Topics
Simulation, Implementation, Brute force, Array
Solved
No attempts yet

Problem

A nonogram (also called paint by numbers, or hanjie) is a logic puzzle that encodes a black and white picture as sequences of numbers. The goal is to rebuild the picture from the numbers alone. The puzzle starts from a blank n×mn \times m grid, and every row and every column carries one sequence of numbers. A sequence lists the lengths of the runs of black squares in that line, read from left to right in a row and from top to bottom in a column. If the numbers of a row are 4 5 1, then the row holds a run of 4 black squares, after it a run of 5 black squares, and after that a run of a single black square. One or more white squares separate two neighboring runs, and zero or more white squares may sit before the first run or after the last run.

If that row has length 13, exactly four layouts fit:

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

Here X is a black square and . is a white square.

Some squares are black in all four layouts, so they are black whichever layout is the real one:

?XXX??XXXX???

A ? marks a square that is black in one layout and white in another.

This is the main technique for solving a nonogram by hand. Filling black squares in one line restricts the layouts of the lines that cross it, which fills more squares there, which restricts the first lines again. White squares come from the same reasoning: a square that is white in every layout of its line agreeing with the squares already fixed is white. Repeating this is enough for many puzzles. Harder puzzles need other methods, but in this problem you use nothing except the technique above.

So a square becomes fixed only when the sequence of its row, or the sequence of its column, together with the squares already fixed in that same line, forces its color. Repeat the deduction over rows and columns until no new square is fixed. The final picture does not depend on the order in which you visit the lines.

Input

The first line holds two integers nn and mm, the number of rows and the number of columns of the grid (1≤n,m≤1001 \le n, m \le 100). Each of the next nn lines describes one row, starting with the uppermost row, in the form p v1 v2 … vpp\ v_1\ v_2\ \ldots\ v_p, where pp is the length of the sequence and v1…vpv_1 \ldots v_p is the sequence itself. A line with no black square is given as a single 0. After those nn lines come mm lines describing the columns in the same form, starting with the leftmost column. The puzzle has at least one arrangement of black and white squares consistent with every sequence, and that arrangement may or may not be fully recoverable with the technique above.

Output

Print the most complete picture the technique above produces, as nn lines of mm characters. Use X for a black square, . for a white square, and ? for a square whose color the technique cannot determine.

Examples2

  1. Example 1

    Input
    3 7
    3 2 1 1
    1 3
    2 2 2
    1 1
    2 1 1
    1 1
    1 2
    1 1
    1 2
    2 1 1
    
    Expected output
    XX.X..X
    ...XXX.
    .XX..XX
    
  2. Example 2

    Input
    5 5
    1 3
    1 3
    1 3
    1 1
    1 1
    1 3
    1 3
    1 3
    1 1
    1 1
    
    Expected output
    ??X??
    ??X??
    XXX..
    ??.??
    ??.??