CrossNumber

You have bet a friend that you can write a program to solve a newspaper CrossNumber puzzle faster than she can solve it by hand.

The puzzle is similar to a crossword, except that each cell contains a digit from $0$ to $9$ instead of a letter. Each clue gives the sum of the digits in the corresponding word. So that it never frustrates the reader, the puzzle is constructed so that throughout the solving process there is always a word with exactly one unfilled cell.

The input consists of several test cases. Each test case begins with an integer $N$ ($2 \le N \le 100$) on a line by itself, giving the number of rows and columns of the square puzzle.

Each test case is described by:

• $N$ rows of $N$ characters each, giving the puzzle grid. The character . denotes an unfilled cell, the character # denotes a black cell, and a digit 0 to 9 denotes the value already assigned to that cell.
• a line containing the word Across.
• one line for each across clue, containing three integers x y sum. Here x and y are the column and row numbers ($1 \le x, y \le N$), and sum is the sum of the digits in that across (or down) word.
• a line containing the word Down.
• one line for each down clue, formatted like an across clue.

Each maximal horizontal or vertical run of non-black cells whose length is at least two has exactly one clue, listed for its top-left square, even if all of its cells are already filled by hints.

A line containing a single 0 marks the end of the input and should not be processed.

For each test case, print the solved grid in the same format ($N$ rows of $N$ characters). Separate the outputs of consecutive puzzles with a single blank line.

The puzzle is guaranteed to have a unique solution.