1075 : 字典序

Description

对于序列 A = (a₁, a₂, …, a_m) 和 B = (b₁, b₂, …, b_m)，定义 A 的字典序比 B 小，记作 A < B ，当且仅当存在 1 ≤ p ≤ m 使得 a_p < b_p 且对于所有的 1 ≤ i < p 都有 a_i = b_i. 进一步地，定义 A ≤ B 当且仅当 A < B 或者 A = B.

Bobo 有一个 n 行 m 列的矩阵 C. 他想找字典序最小的 1, 2, …, m 的排列 σ₁, σ₂, …, σ_m, 使得 S₁ ≤ S₂ ≤ … ≤ S_n，其中 S_i = (C_i, σ1, C_i, σ2, …, C_i, σm).

Input

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

每组数据的第一行包含两个整数 n 和 m.

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

• 1 ≤ n, m ≤ 2000
• 1 ≤ C_i, j ≤ 10⁹
• n × m 的总和不超过 10⁷

Output

对于每组数据，如果有解，输出 m 个整数，表示字典序最小的 σ₁, σ₂, …, σ_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

Source

Author

ftiasch