题目描述

正の整数 $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}$ $\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$)

最後の二条件を満たす最適解が存在することは証明できる。

题目大意

给定 $n\times m$ 的矩阵 $a$，要求构造两个单调递增的整数序列 $x$、$y$，其中 $x$ 的长度为 $n$，$y$ 的长度为 $m$，且两个数列的所有元素均在 $[1,2\times10^9]$ 之间。你需要最小化 $|a_{i,j}-x_iy_j|$ 的最大值。多解任意输出。

1 1
853922530

0
31415
27182

3 3
4 4 4
4 4 4
4 4 4

5
1 2 3 
1 2 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$)
• 入力中の値は全て整数である。