题目描述

给定一个 $R\times C$ 的矩阵，有些格子已经填有了数字；而有些格子为空，用 . 表示。

你需要找到一种填数的方案，使得每行每列的数字依次排列构成的数列为等差数列。

输入格式

输入第一行两个整数 $R,C$，表示矩阵的长和宽。

接下来的 $R$ 行，每行 $C$ 个数字或者字符：. 或者一个数字。

输出格式

输出共 $R$ 行，每行 $C$ 个整数或者分数，表示完善后的矩阵。

分数的格式为 N/D ，其中 $N,D$ 为整数且互质，如果 $D=1$ 则省略。

如果答案不存在，输出 No solution.

输出中的所有数都不超过 $20$ 位。

注意：数据保证输入一定是整数，但输出可能为实数，需要用分数表示。可能有多种方案，输出任意一种即可，本题使用 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

提示

【样例解释】

样例 1 解释

我们可以先把第二行第五列的 $6$ 填入，然后再填写第一行、第二行，最后填写第一列、第四列。

样例 4 提示

输出为多种可能的解决方案中的一种。

【数据规模与约定】

本题使用捆绑测试。

数据共分为以下 $10$ 个子任务，每个子任务 $10$ 分。

子任务编号	限制
$1$	数字已经全部填好
$2$	$R=1$ 或 $C=1$
$3$	$R=C=2$
$4$	保证方案唯一且可使用样例 $1$ 的解决方法
$5$	保证方案唯一且答案中仅包含整数
$6$	保证方案唯一
$7$	每组数据仅可能有唯一的只包含整数的解决方案或者无解
$8$	每组数据仅有唯一的解决方案或者无解
$9$	无特殊限制
$10$

• 在子任务 $1\sim 9$ 中，保证 $1\le R,C\le 6$。
• 对于全部的测试点，保证 $1 \leq R, C \leq 50$，矩阵中给出的所有数字在 $-100\sim 100$ 之间。

【说明】

题目译自 CEOI 2010 day 1 T2 arithmetic。

翻译版权为题目提供者

。

SPJ 由 @一扶苏一 提供，特别鸣谢。