수열 $A = (a_1, a_2, \dots, a_m)$과 $B = (b_1, b_2, \dots, b_m)$에 대해, $a_p < b_p$이고 모든 $1 \leq i < p$에 대해 $a_i = b_i$인 $1 \leq p \leq m$이 존재할 때, 그리고 그때에만 $A$가 $B$보다 사전순으로 작다고 정의하고 $A < B$로 표기한다. 또한 $A < B$ 또는 $A = B$일 때, 그리고 그때에만 $A \leq B$라고 정의한다.

Bobo는 $n$개의 행과 $m$개의 열을 가진 행렬 $C$를 가지고 있다. 그는 $S_1 \leq S_2 \leq \dots \leq S_n$을 만족하는 $1, 2, \dots, m$의 순열 $\sigma_1, \sigma_2, \dots, \sigma_m$ 중 사전순으로 가장 작은 것을 찾고 싶다. 여기서 $S_i = (C_{i, \sigma_1}, C_{i, \sigma_2}, \dots, C_{i, \sigma_m})$이다.

입력

입력 파일에는 여러 테스트 케이스가 있다. 파일의 끝까지 처리한다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $n$과 $m$이 주어진다.

다음 $n$개의 줄 중 $i$번째 줄에는 $m$개의 정수 $C_{i, 1}, C_{i, 2}, \dots, C_{i, m}$이 주어진다.

• $1 \leq n, m \leq 2000$
• $1 \leq C_{i, j} \leq 10^9$
• $n \times m$의 합은 $10^7$을 넘지 않는다.

출력

각 테스트 케이스에 대해 해가 존재하면 사전순으로 가장 작은 $\sigma_1, \sigma_2, \dots, \sigma_m$을 나타내는 $m$개의 정수를 출력한다. 그렇지 않으면 -1을 출력한다.

예제

입력 1

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

출력 1

2 1 3
1 2
-1