Description

You are given an $R \times C$ matrix. Some cells are already filled with numbers, and some cells are empty, represented by ..

You need to find a way to fill in the matrix so that the sequence formed by the numbers in each row (in order) and each column (in order) is an arithmetic progression.

Input Format

The first line contains two integers $R, C$, representing the number of rows and columns of the matrix.

The next $R$ lines each contain $C$ numbers or characters: . or a number.

Output Format

Output $R$ lines in total, each containing $C$ integers or fractions, representing the completed matrix.

The fraction format is N/D, where $N$ and $D$ are coprime integers. If $D = 1$, omit /D.

If no solution exists, output No solution.

All numbers in the output do not exceed $20$ digits.

Note: The testdata guarantees that all input numbers are integers, but the output may contain real numbers, which must be represented as fractions. There may be multiple valid solutions; output any one. This problem uses SPJ.

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

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

1 6
4 . . 0 . 

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

1 4
1 2 . 2

No solution.

3 3
1 . .
. 2 .
. . 3

1 2 3
1 2 3
1 2 3

Hint

Sample Explanation

Sample 1 Explanation

We can first fill in $6$ at row 2, column 5, then fill in the first row and the second row, and finally fill in the first column and the fourth column.

Sample 4 Hint

The output is one of multiple possible solutions.

Constraints

This problem uses bundled testdata.

The testdata is divided into the following $10$ subtasks, each worth $10$ points.

• In subtasks $1 \sim 9$, it is guaranteed that $1 \le R, C \le 6$.
• For all test points, it is guaranteed that $1 \leq R, C \leq 50$, and all given numbers in the matrix are between $-100 \sim 100$.

Notes

This problem is translated from CEOI 2010 day 1 T2 arithmetic.

The translation copyright belongs to the problem provider

The SPJ is provided by @一扶苏一. Special thanks.

Translated by ChatGPT 5