P14342 [JOISC 2019] 馕 / Naan

JOI 咖喱店以供应非常长的馕而闻名。他们有 $L$ 种口味，编号从 $1$ 到 $L$，分别对应不同口味的馕。“JOI 特制馕”是该店最受欢迎的菜品。馕的长度为 $L$ 厘米。我们定义“位置 $x$”为距离馕左端 $x$ 厘米处的位置。位置 $j-1$ 与位置 $j$ 之间的线段由第 $j$ 种口味调味（$1 \le j \le L$）。 有 $N$ 个人来到 JOI 咖喱店。他们的口味偏好各不相同。具体而言，当第 $i$ 个人（$1 \le i \le N$）食用第 $j$ 种口味的馕（$1 \le j \le L$）时，他每厘米可获得 $V_{i,j}$ 的幸福感。 他们只点了一份“JOI 特制馕”。他们将按以下方式分享这份馕： 1. 选择 $N-1$ 个有理数 $X_1, \ldots, X_{N-1}$，满足 $0 < X_1 < X_2 < \cdots < X_{N-1} < L$。 2. 选择 $N$ 个整数 $P_1, \ldots, P_N$，它们构成 $1, \ldots, N$ 的一个排列。 3. 对于每个 $k$（$1 \le k \le N-1$），在位置 $X_k$ 处切开馕。这样，馕将被分成 $N$ 块。 4. 对于每个 $k$（$1 \le k \le N$），将位置 $X_{k-1}$ 与位置 $X_k$ 之间的那块馕分给第 $P_k$ 个人。我们约定 $X_0 = 0$，$X_N = L$。 我们希望公平地分配这份馕。我们称一种分配方式是**公平**的，当且仅当每个人获得的幸福感不少于他独自食用整份“JOI 特制馕”时所获得幸福感的 $\frac{1}{N}$。 编写一个程序，在给定 $N$ 个人的口味偏好信息后，判断是否可能以公平的方式分配馕；若可能，找出一种公平的分配方案。

从标准输入读取以下数据。输入中的所有数值均为整数。 $N\ L$ $V_{1,1}\ V_{1,2}\ \cdots\ V_{1,L}$ $\vdots$ $V_{N,1}\ V_{N,2}\ \cdots\ V_{N,L}$

向标准输出写入结果。若无法以公平方式分配馕，请在一行中输出 $-1$。若可以公平分配，则输出 $N-1$ 个有理数 $X_1, \ldots, X_{N-1}$ 和 $N$ 个整数 $P_1, \ldots, P_N$，它们代表一种公平的分配方案，输出格式如下： $A_1\ B_1$ $A_2\ B_2$ $\vdots$ $A_{N-1}\ B_{N-1}$ $P_1\ P_2\ \cdots\ P_N$ 其中，$A_k$ 和 $B_k$ 是一对整数，满足 $X_k = \frac{A_k}{B_k}$（$1 \le k \le N-1$）。这些整数需满足“输出约束”部分的要求。

### 样例 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 解释 在本样例中，馕只有一种口味。若将馕平均分成 7 块，则无论 $P_1, \ldots, P_N$ 如何取值，该分配都是公平的。 ### 样例 3 解释 请注意 $A_k$ 和 $B_k$ 可以不互质（$1 \leq k \leq N-1$）。 ### 输入限制 - $2 \le N \le 2000$。 - $1 \le L \le 2000$。 - $1 \le V_{i,j} \le 100\,000$（$1 \le i \le N$，$1 \le j \le L$）。 ### 输出限制 若可以公平分配馕，则输出必须满足以下约束： - $1 \le B_k \le 1\,000\,000\,000$（$1 \le k \le N-1$）。 - $0 < \frac{A_1}{B_1} < \frac{A_2}{B_2} < \cdots < \frac{A_{N-1}}{B_{N-1}} < L$。 - $P_1, \ldots, P_N$ 是 $1, \ldots, N$ 的一个排列。 - 在该分配方案中，第 $i$ 个人获得的幸福感不少于 $\frac{V_{i,1} + V_{i,2} + \cdots + V_{i,L}}{N}$（$1 \le i \le N$）。 $A_k$ 和 $B_k$ 不必互质（$1 \le k \le N-1$）。 在输入约束下，可以证明：若存在公平分配方案，则必存在一个满足 $1 \le B_k \le 1\,000\,000\,000$（$1 \le k \le N-1$）的正确输出。 ### 子任务 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 分）无额外约束。 翻译由 Qwen3-235B 完成