← 返回题目列表

Codeforces · 509/D

D. 恢复号码

中文机器翻译题面 查看原题

Vasya 有两个由非负整数组成的数组:大小为 n 的 a 和大小为 m 的 b。 Vasya 选择一个正整数 k 并使用以下公式创建一个 n × m 矩阵 v:

$$v_{i,j} = (a_i + b_j) \bmod k$$

Vasya 在一张纸上写下了矩阵 v 并将其放入表格中。

一年后,Vasya 在清理桌子时发现了一张包含 n × m 矩阵 w 的纸。他记得有一天按照上面给出的规则制作了一个矩阵,但他不确定是否找到了当时写有矩阵 v 的论文。你的任务是找出你找到的矩阵 w 是否可以通过遵循这些规则获得,如果可以,那么对于什么数字 k, a1, a2, ..., an, b1, b2, ..., bm 是可能的。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 100),用空格分隔 - 分别是找到的矩阵中的行数和列数。

以下第 i 行包含数字 wi, 1, wi, 2, ..., wi, m (0 ≤ wi, j ≤ 109),用空格分隔 — 矩阵 w 第 i 行的元素。

输出

如果无法通过上述方式获得矩阵 w,则在单行输出中打印“NO”(不带引号)。

否则,打印四行。

在第一行打印“YES”(不带引号)。

在第二行中打印一个整数 k (1 ≤ k ≤ 1018)。请注意,表 w 的每个元素应在 0 和 k - 1 之间(包括 0 和 k - 1)。

在第三行打印 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 1018),用空格分隔。

在第四行中打印 m 个整数 b1, b2, ..., bm (0 ≤ bi ≤ 1018),用空格分隔。

示例

输入 #1

2 3
1 2 3
2 3 4

输出 #1

YES
1000000007
0 1
1 2 3

输入 #2

2 2
1 2
2 0

输出 #2

YES
3
0 1
1 2

输入 #3

2 2
1 2
2 1

输出 #3

NO

注意

通过 $$b \mod c$$ 我们表示 b 除以 c 的整数除法的余数。

可以保证,如果存在一组数字 k, a1, ..., an, b1, ..., bm,可用于创建矩阵 w,则在输出格式中也存在一组满足限制 1 ≤ k ≤ 1018, 1 ≤ ai ≤ 1018, 1 ≤ bi ≤ 1018 的数字。换句话说,引入这些上限只是为了检查方便。