题目描述

有正整数 $N, M$，以及一个 $N \\times M$ 的正整数矩阵 $A_{i, j}$。对于两个严格递增的正整数序列 $X = (X_1, \\ldots, X_N)$ 和 $Y = (Y_1, \\ldots, Y_M)$，我们定义罚分 $D(X, Y)$ 为 $\\max_{1 \\leq i \\leq N, 1 \\leq j \\leq M} |X_i Y_j - A_{i, j}|$。

找到两个严格递增的正整数序列 $X$ 和 $Y$，使得 $D(X, Y)$ 最小。

约束条件

• $1 \\leq N, M \\leq 5$
• $1 \\leq A_{i, j} \\leq 10^9$ ($1 \\leq i \\leq N$, $1 \\leq j \\leq M$)
• 输入的所有值都是整数。

输入

从标准输入按以下格式给出输入：

$N$ $M$ $A_{1,1}$ $\\ldots$ $A_{1,M}$ $\\vdots$ $A_{N,1}$ $\\ldots$ $A_{N,M}$

输出

按以下格式输出答案：

$D_{min}$ $X_1$ $\\ldots$ $X_N$ $Y_1$ $\\ldots$ $Y_M$

其中，$D_{min}$ 是最小可能的罚分，需要满足以下条件：

• $D(X, Y)$ 等于 $D_{min}$。
• $X_i < X_{i + 1}$ ($1 \\leq i \\leq N - 1$)。
• $Y_j < Y_{j + 1}$ ($1 \\leq j \\leq M - 1$)。
• $1 \\leq X_i \\leq 2\\cdot 10^9$ ($1 \\leq i \\leq N$)。
• $1 \\leq Y_j \\leq 2\\cdot 10^9$ ($1 \\leq j \\leq M$)。

可以证明存在一个满足最后两个条件的最优解。

示例输入 1

1 1
853922530

示例输出 1

0
31415
27182

示例输入 2

3 3
4 4 4
4 4 4
4 4 4

示例输出 2

5
1 2 3 
1 2 3 

示例输入 3

3 4
4674 7356 86312 100327
8737 11831 145034 167690
47432 66105 809393 936462

示例输出 3

357
129 216 1208 
39 55 670 775