数列 $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})$ です。

入力

入力ファイルには複数のテストケースが含まれます。ファイルの終わりまで処理してください。

各テストケースの 1 行目には 2 個の整数 $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