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$）的馕时，每 $1$ 厘米他们将获得 $V_{i,j}$ 的幸福度。
他们只点了一份 JOI 特制馕。他们将按以下方式分享这个馕：
- 选择 $N-1$ 个有理数 $X_1, \dots, X_{N-1}$，满足 $0 < X_1 < X_2 < \dots < X_{N-1} < L$。
- 选择 $N$ 个整数 $P_1, \dots, P_N$，它们构成 $1, \dots, N$ 的一个排列。
- 对于每个 $k$（$1 \le k \le N-1$），在位置 $X_k$ 处切开馕。这样，馕将被分成 $N$ 块。
- 对于每个 $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} \ \dots \ V_{1,L}$ $\vdots$ $V_{N,1} \ V_{N,2} \ \dots \ V_{N,L}$
输出格式
输出到标准输出。如果无法以公平的方式分配馕，则输出 $-1$。如果可以，输出 $N-1$ 个有理数 $X_1, \dots, X_{N-1}$ 和 $N$ 个整数 $P_1, \dots, P_N$，表示一种公平的分配，格式如下：
$A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_{N-1} \ B_{N-1}$ $P_1 \ P_2 \ \dots \ P_N$
其中 $A_k$ 和 $B_k$ 是满足 $X_k = \frac{A_k}{B_k}$ 的一对整数（$1 \le k \le N-1$）。这些整数必须遵循“输出限制”部分的要求。
数据范围
- $2 \le N \le 2\,000$
- $1 \le L \le 2\,000$
- $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} < \dots < \frac{A_{N-1}}{B_{N-1}} < L$
- $P_1, \dots, P_N$ 是 $1, \dots, N$ 的一个排列
- 在该分配中，第 $i$ 个人获得的幸福度大于或等于 $\frac{V_{i,1} + V_{i,2} + \dots + 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$）的正确输出。
子任务
- （5 分）$N = 2$
- （24 分）$N \le 6, V_{i,j} \le 10$（$1 \le i \le N, 1 \le j \le L$）
- （71 分）无附加限制
样例
样例输入 1
2 5 2 7 1 8 2 3 1 4 1 5
样例输出 1
14 5 2 1
样例输入 2
7 1 1 2 3 4 5 6 7
样例输出 2
1 7 2 7 3 7 4 7 5 7 6 7 3 1 4 2 7 6 5
样例输入 3
5 3 2 3 1 1 1 1 2 2 1 1 2 2 1 2 1
样例输出 3
15 28 35 28 50 28 70 28 3 1 5 2 4
说明
注意 $A_k$ 和 $B_k$ 不需要互质（$1 \le k \le N-1$）。