CSG-CPC
Online Judge

1075 : 字典序

         Time Limit: 5 Sec     Memory Limit: 512 Mb     Submitted: 37     Solved: 6    

Description

对于序列 A = (a1, a2, …, am)B = (b1, b2, …, bm),定义 A 的字典序比 B 小,记作 A < B ,当且仅当存在 1 ≤ p ≤ m 使得 ap < bp 且对于所有的 1 ≤ i < p 都有 ai = bi. 进一步地,定义 A ≤ B 当且仅当 A < B 或者 A = B.

Bobo 有一个 nm 列的矩阵 C. 他想找字典序最小的 1, 2, …, m 的排列 σ1, σ2, …, σm, 使得 S1 ≤ S2 ≤ … ≤ Sn,其中 Si = (Ci, σ1, Ci, σ2, …, Ci, σm).

Input

输入文件包含多组数据,请处理到文件结束。

每组数据的第一行包含两个整数 nm.

接下来 n 行,其中第 i 行包含 m 个整数 Ci, 1, Ci, 2, …, Ci, m.

  • 1 ≤ n, m ≤ 2000
  • 1 ≤ Ci, j ≤ 109
  • n × m 的总和不超过 107

Output

对于每组数据,如果有解,输出 m 个整数,表示字典序最小的 σ1, σ2, …, σm. 否则输出 -1.

Sample

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
2 1 3
1 2
-1

Hint

Author

ftiasch