题目描述

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$）。这些整数需满足“输出约束”部分的要求。

2 5
2 7 1 8 2
3 1 4 1 5

14 5
2 1

7 1
1
2
3
4
5
6
7

1 7
2 7
3 7
4 7
5 7
6 7
3 1 4 2 7 6 5

5 3
2 3 1
1 1 1
2 2 1
1 2 2
1 2 1

15 28
35 28
50 28
70 28
3 1 5 2 4

提示

样例 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 完成