AT_joisc2019_c.ナン (Naan)

题目译自 JOISC 2019 Day1 T3「ナン / Naan」

JOI 咖喱店以提供很长（？）的馕而闻名。它提供的馕有 $L$ 种口味，编号从 $1$ 到 $L$。「JOI 特色馕」是店内最受欢迎的一道菜。馕的总长度为 $L$ 厘米。我们定义「点 $X$」为馕上距离馕左端 $X$ 厘米处的点。对于 $1 \le j \le L$，点 $j-1$ 和点 $j$ 间的一段馕是第 $j$ 种口味的。

有 $N$ 个人来到了 JOI 咖喱店，他们每个人的偏好都不同，具体的说，第 $i$ 个人每吃一厘米的风味 $j$ 的馕，就会获得 $V_{i,j}$ 的快乐度。

他们只买了一个 JOI 特色馕，他们将用下面的方式分享馕：

1. 选择 $N-1$ 个分数 $X_1, \ldots, X_{N-1}$，满足 $0 < X_1 < X_2 < \ldots < X_{N-1} < L$。
2. 选择 $N$ 的一个排列 $P_1, \ldots P_N$。
3. 对于每一个 $k (1 \le k \le N-1)$，在点 $X_k$ 的位置切一刀，然后馕将被切成 $N$ 个部分。
4. 第 $k (1 \le k \le N)$ 个部分的左端点为 $X_{k-1}$，右端点为 $X_{k}$，这里我们认为 $X_0=0, X_N=L$。
5. 第 $P_i$ 个人将吃掉第 $i$ 个部分。

现在他们想公平的分配馕，他们认为一种分配方法是公平的，当且仅当每个人获得的快乐度都不小于他们独吞整个馕所获得的快乐度的 $\frac{1}{N}$。

现在给你 $N$ 个人的信息，你需要判断是否存在一种公平的分配方式，如果存在，输出一组分配方案。

从标准输入中读取数据。

第一行两个整数 $N, L$。
接下来 $N$ 行，每行 $L$ 个整数，第 $i$ 行第 $j$ 个数为 $V_{i,j}$。

输出数据到标准输出中。

如果无解，输出一行 -1；

如果有解，首先输出 $N-1$ 行，第 $i$ 行两个整数 $A_i, B_i$，要求 $A_i, B_i$ 是一对满足 $X_i = \frac{A_i}{B_i} (1 \le i \le N)$ 的整数对。

接下来一行 $N$ 个整数，第 $i$ 个数表示 $P_i$。

你的输出需要满足：

• $1 \le B_i \le 10^9 (1 \le i \le N)$。
• $0 < \frac{A_1}{B_1} < \frac{A_2}{B_2} < ... < \frac{A_{N-1}}{B_{N-1}} < L$。
• $P_1, ... ,P_N$ 是一个 $1, ..., N$ 的排列。
• 第 $i$ 个人获得的总快乐度不小于 $\frac{V_{i,1}+V_{i,2}+...+V_{i,L}}{N} (1 \le i \le N)$。
• $A_i, B_i$ 不必互质。

可以证明，如果输入数据有解，那么一定存在一组满足上述条件的解。

样例解释 1

在这组样例中，第一个人如果吃掉整个馕，会得到 $2+7+1+8+2=20​$ 的快乐度，第二个人如果吃掉整个馕，会获得 $3+1+4+1+5=14​$ 的快乐度。因此，如果第一个人获得不小于 $\frac{20}{2}=10​$ 的快乐度，且第二个人获得不小于 $\frac{14}{2}=7​$ 的快乐度，就是一组合法的解。

如果在点 $\frac{14}{5}$ 的位置切一刀，第一个人会获得 $1 \times \frac{1}{5} + 8 + 2 = \frac{51}{5}$ 的快乐度，第二个人会获得 $3+1+4 \times \frac{4}{5} = \frac{36}{5}$ 的快乐度。因此这是一组合法的解。

样例解释 2

在这组样例中，馕只有一种风味。只要把馕七等分，就是合法的方案，与 $P_1, ..., P_N$ 无关。

样例解释 3

注意 $A_i, B_i (1 \le i \le N)$ 不必互质。

数据范围

Subtask #	分值	数据规模
1	5	$N = 2$
2	24	$N \le 6,V_{i,j} \le 10 (1 \le i \le N,1 \le j \le L)$
3	71	无特殊限制

对于所有输入数据，有 $1 \le N \le 2000,1 \le L \le 2000, 1 \le V_{i,j} \le 10^5 (1 \le i \le N,1 \le j \le L)$。

翻译来自于 LibreOJ。