Data Recovery

Interview

Time limit5sMemory limit128 MB

Summary

Given a grid with some unknown cells plus all row and column sums, print each unknown cell's forced value, or -1 if several values fit.

Level: Medium6 of 10
Topics: Graph, Prefix sum, Greedy, Implementation
Solved: No attempts yet

Problem

James recorded important company data in a table whose every cell holds an integer from 0 to 100. For his statistics he also wrote down the sum of each row and the sum of each column.

On the way to a meeting the paper got rained on, and some cells became unreadable — but the row and column sums survived. James wants to recover as much of the table as he can. A cell that is still legible has a known value; for an unreadable cell, the row and column sums may pin its value down exactly, or they may leave several possibilities.

For each cell, decide whether its value is forced by the legible cells together with all the row and column sums.

Input

The input contains several test cases. Each test case begins with a line containing two integers $N$ and $M$ ( $1 \le N, M \le 50$ ), the table's dimensions. The next $N$ lines each contain $M$ integers: a value from 0 to 100 for a still-legible cell, or $-1$ for an unreadable cell.

After the table come two more lines. The first has $N$ integers — the sum of each row, from top to bottom. The second has $M$ integers — the sum of each column, from left to right. Every row and column sum is between 0 and 5000.

The input ends with a line containing two zeros, which is not a test case.

Every given table is guaranteed to be valid: the unreadable cells can be filled with integers from 0 to 100 so that all row and column sums match.

Output

For each test case, print $N$ lines of $M$ entries each, describing the recovered table.

For a cell that was legible in the input, print its given value. For an unreadable cell, if exactly one integer from 0 to 100 is consistent with all the legible cells and all the row and column sums, print that unique integer; otherwise print $-1$ .

Separate consecutive entries on a line with a single space, with no trailing space, and print no blank lines between test cases.

Examples1

Example 1

Input

2 2
1 -1
-1 -1
100 100
100 100
5 5
-1 -1 6 -1 8
-1 -1 0 4 2
3 -1 -1 5 -1
4 0 2 -1 -1
2 1 5 -1 -1
21 10 15 13 14
18 6 17 15 17
2 3
1 2 3
3 5 6
6 14
4 7 9
0 0

Expected output

1 99
99 1
-1 -1 6 0 8
-1 -1 0 4 2
3 3 4 5 0
4 0 2 -1 -1
2 1 5 -1 -1
1 2 3
3 5 6