시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 5 5 5 100.000%

문제

JOI Curry Shop is famous for serving very long naans. They have L kinds of flavors, numbered from 1 through L, to flavor naans. “JOI Special Naan” is the most popular menu in the shop. The length of the naan is L cm. We define “the position x” as the position on the naan which is x cm distant from the left end of the naan. The segment between position j − 1 and position j is flavored by flavor j (1 ≤ j ≤ L).

N people came to JOI Curry Shop. Their preferences are different from each other. Specifically, when the i-th (1 ≤ j ≤ L) person eats naan with flavor j (1 ≤ j ≤ L), they will get happiness Vi, j per 1 cm. They ordered only one JOI Special Naan. They will share the naan in the following manner:

1. Choose N − 1 rational numbers X1, . . . , XN−1 which satisfy 0 < X1 < X2 < · · · < XN−1 < L.
2. Choose N integers P1, . . . , PN which form a permutation of 1, . . . , N.
3. For each k (1 ≤ k ≤ N − 1), cut the naan at the position Xk. Thus, the naan will be separated into N pieces.
4. For each k (1 ≤ k ≤ N), give the piece between the position Xk−1 and position Xk to the Pk-th person. We consider X0 as 0 and XN as L.

We want to distribute the naan fairly. We say a distribution is fair if each person gets happiness of more than or equal to 1 N of the amount of happiness they will get by eating the whole JOI Special Naan.

Write a program which, given the information of preferences of N people, determines if it is possible to distribute the naan in a fair way, and if it is possible, finds such a fair way.

입력

Read the following data from the standard input. All the values in the input are integers.

N L
V1,1 V1,2 · · · V1,L
.
.
.
VN,1 VN,2 · · · VN,L

출력

Write to the standard output. If it is impossible to distribute naan in a fair way, write −1 in a line. If it is possible, output N − 1 rational numbers X1, . . . , XN−1 and N integers P1, . . . , PN which represent a fair distribution, in the following format.

A1 B1
A2 B2
.
.
.
AN−1 BN−1
P1 P2 · · · PN

Ak and Bk are a pair of integers which satisfies Xk = Ak/Bk (1 ≤ k ≤ N − 1).

If it is possible to distribute the naan in a fair way, the output must satisfy the following constraints:

• 1 ≤ Bk ≤ 1 000 000 000 (1 ≤ k ≤ N − 1).
• 0 < A1/B1 < A2/B2 < · · · < AN−1/BN−1 < L.
• P1, . . . , PN is a permutation of 1, . . . , N.
• In the distribution, the amount of happiness which i-th person will get is more than or equal to (Vi,1 + Vi,2 + · · · + Vi,L)/N (1 ≤ i ≤ N).

Ak and Bk are not necessary to be coprime (1 ≤ k ≤ N − 1). Under the constraints of the input, it can be proved that if a fair distribution exists, there is a correct output which satisfies 1 ≤ Bk ≤ 1 000 000 000 (1 ≤ k ≤ N − 1).

제한

• 2 ≤ N ≤ 2 000.
• 1 ≤ L ≤ 2 000.
• 1 ≤ Vi, j ≤ 100 000 (1 ≤ i ≤ N, 1 ≤ j ≤ L).

예제 입력 1

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


예제 출력 1

14 5
2 1


In this sample, the first person will get happiness of 2 + 7 + 1 + 8 + 2 = 20 when she eats the whole naan and the second person will get happiness of 3 + 1 + 4 + 1 + 5 = 14 when she eats the whole naan. Thus, if the first person gets happiness of more than or equal to 20/2 = 10 and the second person gets happiness of more than or equal to 14/2 = 7, the distribution is fair.

If you cut the naan at the position 14/5 , the first person will get happiness of 1 × 1/5 + 8 + 2  = 51/5 and the second person will get happiness of 3 + 1 + 4 × 4/5 = 36/5. Hence, this is a fair distribution.

예제 입력 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


In this sample, the naan has only one flavor. If you equally divide the naan into 7 pieces, the distribution will be fair, regardless of P1, . . . , PN.

예제 입력 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


Note that Ak and Bk are not necessary to be coprime (1 ≤ k ≤ N − 1).