Sum and Game Solver

This problem is a variant of the Kakuro puzzle. You are given an M×N board where each cell is either a white cell or a gray cell. White cells must be filled with a number from 1 to 9. Gray cells contain clues. A gray cell is divided by a diagonal into two halves: the lower‐left half (denoted by A) and the upper‐right half (denoted by B).

For a gray cell:

• If its A value is nonzero, then the contiguous white cells immediately below that gray cell (i.e. starting from the cell directly beneath, and continuing downward until a non‐white cell or board border is reached) must sum to the A value. The numbers in that vertical "entry" must all be distinct.
• If its B value is nonzero, then the contiguous white cells immediately to the right of that gray cell (i.e. starting from the cell directly to the right, and continuing right until a non‐white cell or board border is reached) must sum to the B value. The numbers in that horizontal "entry" must all be distinct.

The board is guaranteed to have a unique solution. Gray cells that do not provide a clue will have both A and B values equal to 0.

The input board uses the following format:

• The first line contains two integers M and N.
• Then M lines follow, each with N tokens separated by spaces. A token is either:
• A single period "." indicating a white cell, or
• A clue in the format X,Y (without spaces) where X and Y are nonnegative integers. X is the A (vertical) clue and Y is the B (horizontal) clue. A value of 0 indicates no clue in that half.

Your task is to fill the white cells with digits from 1 to 9 so that all clues are satisfied.

Once solved, output the board in the same format as the input except that each white cell token (originally a period) is replaced by the digit that you have assigned to that cell. Gray cells must be output unchanged.

Note: Every "entry" (i.e. every contiguous sequence of white cells as described) must have all distinct digits and its digits must sum exactly to the clue given in the corresponding half of the gray cell.

inputFormat

The first line contains two integers M and N, indicating the number of rows and columns respectively. The following M lines each contain N tokens separated by spaces. Each token is either a dot (.) representing a white cell, or a clue in the form X,Y representing a gray cell, where X is the A value (vertical clue) and Y is the B value (horizontal clue). A value of 0 indicates that there is no clue in that half.

outputFormat

Output M lines. For each cell, if it is a white cell, output the digit (1..9) assigned to that cell; if it is a gray cell, output the token exactly as given in the input. Separate tokens in one line by a single space.

sample

5 5
0,0 5,0 0,0 3,0 0,0
0,5 . 0,3 . 0,0
0,0 8,0 0,0 1,0 0,0
0,8 . 0,1 . 0,0
0,0 0,0 0,0 0,0 0,0

0,0 5,0 0,0 3,0 0,0
0,5 5 0,3 3 0,0
0,0 8,0 0,0 1,0 0,0
0,8 8 0,1 1 0,0
0,0 0,0 0,0 0,0 0,0