题目描述

给定正整数 $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}|$。

请你求出能够最小化 $D(X, Y)$ 的两个严格单调递增正整数序列 $X,\ Y$。

输入格式

输入从标准输入读入，格式如下：

$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\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

输出

0
31415
27182

样例 2

输入

3 3
4 4 4
4 4 4
4 4 4

输出

5
1 2 3 
1 2 3

样例 3

输入

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

输出

357
129 216 1208 
39 55 670 775

说明/提示

限制条件

• $1 \leq N, M \leq 5$
• $1 \leq A_{i,j} \leq 10^9$（$1 \leq i \leq N$，$1 \leq j \leq M$）
• 输入中的所有数值均为整数。

由 ChatGPT 4.1 翻译