An Arithmetic Rectangle

Memory limit: 256 MB

After the lesson on arithmetic progressions, the teacher gave Peter homework: a sheet of paper with numbers written in some cells of a 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:

Peter is lazy to do such tasks manually. He wants you to write a program that will do it for him.

Task

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 one integer (): the number of test cases. The following lines contain the descriptions of the test cases.

The first line of a test case description contains two positive integers and : the dimensions of the grid. lines follow, each of them containing 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 10 points each. In batches 1 through 9 we have . The properties of the individual batches are given below.
Batch 1. All numbers are already filled in.
Batch 2. Either or in each test case.
Batch 3. 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 .

Output

Your program should output the results to the respective test cases in the following format.

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 for a test case, output rows, each with 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.)

Examples

For the input data:

1
3 5
. . 3 . 5
. . . 5 .
. . . . 7

the correct result is:

1 2 3 4 5
2 3 4 5 6
3 4 5 6 7

The above example can be solved as follows: First, note that the second number in the last column must be 6. Then fill in row 1, row 2, and finally fill in columns 1 through 4.

For the input data:

1
1 6
4 . . 0 . .

the correct result is:

4 8/3 4/3 0 -4/3 -8/3

For the input data:

1
1 4
1 2 . 2

the correct result is:

No solution.

For the input data:

1
3 3
1 . .
. 2 .
. . 3

the correct result is:

1 0 -1
3 2 1
5 4 3

This is one of many possible solutions for this input.

Task author: Michal Forisek.