Problem Description

Given an $R \times C$ matrix, some cells are already filled with numbers, while others are empty, represented by . characters.

You need to find a way to fill the empty cells such that each row and each column forms an arithmetic sequence.

Input Format

The first line of input contains two integers $R$ and $C$, representing the height and width of the matrix.

The following $R$ lines each contain $C$ elements, which can be either a number or a . character.

Output Format

The output should consist of $R$ lines, each containing $C$ integers or fractions, representing the completed matrix.

Fractions should be formatted as N/D, where $N$ and $D$ are coprime integers, and if $D=1$, it should be omitted.

If no solution exists, output No solution.

All numbers in the output should not exceed 20 digits.

Note: The input is guaranteed to be integers, but the output may be real numbers, which need to be represented as fractions. There may be multiple solutions; any valid one will be accepted. This problem uses a special judge (SPJ).

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

1 6
4 . . 0 . 

Sample Output #2

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

Sample Input #3

1 4
1 2 . 2

Sample Output #3

No solution.

Sample Input #4

3 3
1 . .
. 2 .
. . 3

Sample Output #4

1 2 3
1 2 3
1 2 3

Notes

Sample Explanation

Sample 1 Explanation

We can first fill in the $6$ at the second row and fifth column, then fill in the first and second rows, and finally fill in the first and fourth columns.

Sample 4 Hint

The output is one of the possible solutions.

Data Constraints and Specifications

This problem uses bundled testing.

There are 10 subtasks, each worth 10 points.

• For subtasks 1 through 9, $1 \leq R, C \leq 6$.
• For all test cases, $1 \leq R, C \leq 50$, and all given numbers in the matrix are between $-100$ and $100$.

Notes

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

Translation rights belong to the problem provider @ShineEternal. Reproduction without permission is prohibited.

The SPJ is provided by @一扶苏一, with special thanks.

见题面 Input 部分

见题面 Output 部分