Quán cà ri JOI nổi tiếng với những chiếc bánh naan rất dài. Quán có \(L\) hương vị, đánh số từ \(1\) đến \(L\). Món được yêu thích nhất là bánh naan đặc biệt JOI, dài \(L\) cm. Vị trí \(x\) trên bánh là điểm cách đầu bên trái \(x\) cm. Đoạn từ vị trí \(j-1\) đến vị trí \(j\) mang hương vị \(j\) (\(1 \le j \le L\)).

Có \(N\) người đến quán, mỗi người có sở thích riêng. Khi người thứ \(i\) ăn \(1\) cm bánh mang hương vị \(j\), người đó nhận được \(V_{i,j}\) đơn vị hạnh phúc (\(1 \le i \le N\), \(1 \le j \le L\)).

Họ chỉ gọi một chiếc bánh naan đặc biệt JOI và chia bánh như sau:

1. Chọn \(N-1\) số hữu tỉ \(X_1,\ldots,X_{N-1}\) sao cho \(0<X_1<X_2<\cdots<X_{N-1}<L\).
2. Chọn một hoán vị \(P_1,\ldots,P_N\) của các số \(1,\ldots,N\).
3. Cắt bánh tại mỗi vị trí \(X_k\) (\(1 \le k \le N-1\)), thu được \(N\) phần.
4. Với mỗi \(1 \le k \le N\), đưa phần bánh từ vị trí \(X_{k-1}\) đến vị trí \(X_k\) cho người thứ \(P_k\). Quy ước \(X_0=0\) và \(X_N=L\).

Một cách chia được gọi là công bằng nếu mỗi người nhận được ít nhất \(\frac{1}{N}\) lượng hạnh phúc mà người đó sẽ nhận khi ăn cả chiếc bánh.

Cho sở thích của \(N\) người, hãy xác định có thể chia bánh công bằng hay không. Nếu có, hãy tìm một cách chia như vậy.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N L
V_{1,1} V_{1,2} ... V_{1,L}
...
V_{N,1} V_{N,2} ... V_{N,L}

Tất cả dữ liệu vào là số nguyên.

Dữ liệu ra

Nếu không có cách chia công bằng, ghi một dòng chứa -1. Ngược lại, ghi:

A_1 B_1
...
A_{N-1} B_{N-1}
P_1 P_2 ... P_N

Trong đó \(A_k,B_k\) là các số nguyên biểu diễn \(X_k=A_k/B_k\) với \(1 \le k \le N-1\). Nếu có nhiều đáp án đúng, có thể ghi bất kỳ đáp án nào.

Ràng buộc

• \(2 \le N \le 2000\).
• \(1 \le L \le 2000\).
• \(1 \le V_{i,j} \le 100\,000\) với \(1 \le i \le N\), \(1 \le j \le L\).

Nếu xuất ra một cách chia, đáp án phải thỏa mãn:

• \(1 \le B_k \le 10^9\) với \(1 \le k \le N-1\).
• \(0<A_1/B_1<A_2/B_2<\cdots<A_{N-1}/B_{N-1}<L\).
• \(P_1,\ldots,P_N\) là một hoán vị của \(1,\ldots,N\).
• Mỗi người thứ \(i\) nhận được lượng hạnh phúc ít nhất \((V_{i,1}+\cdots+V_{i,L})/N\) với \(1 \le i \le N\).

Không yêu cầu \(A_k\) và \(B_k\) nguyên tố cùng nhau. Với các ràng buộc đầu vào trên, nếu tồn tại cách chia công bằng thì luôn tồn tại một đáp án đúng có mọi mẫu số không vượt quá \(10^9\).

Phân nhóm

1. (5 điểm) \(N=2\).
2. (24 điểm) \(N \le 6\) và \(V_{i,j} \le 10\) với mọi \(1 \le i \le N\), \(1 \le j \le L\).
3. (71 điểm) Không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 1. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.