For sequences $A = (a_1, a_2, \dots, a_m)$ and $B = (b_1, b_2, \dots, b_m)$, we define $A$ to be lexicographically smaller than $B$, denoted as $A < B$, if and only if there exists $1 \leq p \leq m$ such that $a_p < b_p$ and $a_i = b_i$ for all $1 \leq i < p$. Furthermore, we define $A \leq B$ if and only if $A < B$ or $A = B$.

Bobo has an $n \times m$ matrix $C$. He wants to find the lexicographically smallest permutation $\sigma_1, \sigma_2, \dots, \sigma_m$ of $1, 2, \dots, m$ such that $S_1 \leq S_2 \leq \dots \leq S_n$, where $S_i = (C_{i, \sigma_1}, C_{i, \sigma_2}, \dots, C_{i, \sigma_m})$.

Input

The input contains multiple test cases. Process until the end of the file.

Each test case starts with two integers $n$ and $m$.

The next $n$ lines each contain $m$ integers $C_{i, 1}, C_{i, 2}, \dots, C_{i, m}$.

• $1 \leq n, m \leq 2000$
• $1 \leq C_{i, j} \leq 10^9$
• The sum of $n \times m$ does not exceed $10^7$

Output

For each test case, if a solution exists, output $m$ integers representing the lexicographically smallest $\sigma_1, \sigma_2, \dots, \sigma_m$. Otherwise, output -1.

Examples

Input 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

Output 1

2 1 3
1 2
-1