난

JOI 카레 매점은 매우 긴 난(인도의 납작한 빵)을 판매하는 것으로 유명하다. 난에는 $L$개의 맛이 있으며, 1번부터 $L$번까지 번호가 붙어 있다. 난 중에서 "JOI 스페셜 난"이 제일 인기가 있다. 길이가 $L$cm 이고, 왼쪽에서 $j-1$cm 부터 $j$cm 까지 부분에는 $j$번 ($1\le j \le L$) 맛으로 되어 있다.

$N$명의 사람이 JOI 카레 매점에 왔다. 그들의 취향은 다른 사람과 다르다. 구체적으로, $i$ 번째 ($1 \le i \le N$) 사람이 $j$번 ($1 \le j \le L$) 맛의 난을 먹었을 경우에는, 1 cm당 $V\_{i, j}$의 행복도를 얻을 것이다. 그들은 하나의 JOI 스페셜 난을 주문했다. 그들은 난을 다음과 같은 방법으로 나누어 가질 것이다.

1. $0 < X\_1 < X\_2 < \cdots < X\_{N-1} < L$을 만족하는 $N-1$개의 분수 $X\_1,\ \cdots,\ X\_{N-1}$를 고른다.
2. $N$개의 정수 $P\_1,\ \cdots, \ P\_N$을 고른다. 이는 $1, \ \cdots, \ N$의 순열이어야 한다.
3. 각 $k$ ($1 \le k \le N-1$)에 대해서, 난을 $X\_k$지점에서 자른다. 난은 $N$개의 조각으로 나누어질 것이다.
4. 각 $k$ ($1 \le k \le N$)에 대해서, $P\_k$번째 사람에게 $X\_{k-1}$과 $X\_k$ 사이의 조각을 준다. 우리는 $X\_0$을 0, $X\_N$을 $L$이라고 생각할 것이다.

우리는 난을 공평하게 나누고 싶다. 우리는 각 사람이 혼자 JOI 스페셜 난을 모두 먹었을 때 얻는 행복도의 $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,\ \cdots,\ X\_{N-1}$과 $N$개의 정수 $P\_1, \cdots, 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\_i$, $B\_i$는 $X\_i = \dfrac{A\_i}{B\_i}$ ($1 \le i \le N$)를 만족하는 정수 쌍이다. 이 정수는 출력 제한을 따라야 한다.

입력 제한

• $1 \le N \le 2000$.
• $0 \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\_i \le 1\ 000\ 000\ 000$. ($1 \le i \le N$)
• $0 \le \dfrac{A\_1}{B\_1} < \dfrac{A\_2}{B\_2} \cdots < \dfrac{A\_{N-1}}{B\_{N-1}} < L$.
• $P\_1, \ \cdots, \ P\_N$은 $1, \ \cdots, \ N$의 순열이다.
• 분배에서, $i$번째 사람이 가지는 행복도의 양은 $\dfrac{V\_{i, 1}+V\_{i,2}+\cdots+V\_{i,L}}{N}$ 이상 이어야 한다.

$A\_i$와 $B\_i$는 서로소일 필요는 없다. 아래 제한 하에서, 공평한 분배가 존재 할 경우 $1 \le B\_i \le 1\ 000\ 000\ 000$을 만족하는 출력이 존재함을 증명할 수 있다.