An Arithmetic Rectangle
After the lesson on arithmetic progressions, the teacher gave Peter homework: a sheet of paper with numbers written in some cells of a R×C grid. Some of the cells were empty. Peter's task is to create an arithmetic rectangle by filling in the missing numbers. In an arithmetic rectangle, all the numbers in each row and in each column have to form an arithmetic progression in the order in which they appear.
For example, this is a arithmetic rectangle:
1 3 5 7 9
2 2 2 2 2
3 1 -1 -3 -5
Peter is lazy to do such tasks manually. He wants you to write a program that will do it for him.
You are given a grid of integers, some of them substituted by dots. Find out whether it is possible to replace the dots by some rational numbers in order to obtain an arithmetic rectangle. If there is a solution, find one.
Note: An arithmetic progression is a sequence of numbers such that the difference of any two successive elements of the sequence is a constant.
Input
The first line of the input contains two positive integers R and C: the dimensions of the grid. R lines follow, each of them containing C tokens separated by single spaces. Each of the tokens is either a dot (.), or an integer.
Constraints
Each number given in the grid is between -100 and 100, inclusive. There are 10 batches of test cases, worth 10points each. In batches 1 through 9 we have 1 ≤ R, C ≤ 6. The properties of the individual batches are given below.
Batch 1. All numbers are already filled in.
Batch 2. Either R = 1 or C = 1 in each test case.
Batch 3. R = C = 2 in each test case.
Batch 4. Each test case has a unique solution that can be found using the approach suggested in the first example.
Batch 5. Each test case has a unique solution, and the solution contains integers only.
Batch 6. Each test case has a unique solution.
Batch 7. Each test case either has a unique solution that contains integers only, or has no solution at all.
Batch 8. Each test case either has a unique solution, or has no solution at all.
Batch 9. Arbitrary test cases.
Batch 10. Arbitrary test cases with 1 ≤ R, C ≤ 50.
Output
If there is no solution, output a single line with the string "No solution." (quotes for clarity). If there are multiple solutions, pick and output any single solution.
When outputting a solution, output R rows, each with C space-separated rational numbers.
Each rational number shall be printed as "N/D", where D is positive and N and D are relatively prime. If D is 1, omit the "/D" part.
No number in your output may have more than 20 digits. (It should be easy to satisfy this restriction, its only intent is to simplify checking your outputs.)