Para las secuencias $A = (a_1, a_2, \dots, a_m)$ y $B = (b_1, b_2, \dots, b_m)$, se define que $A$ es lexicográficamente menor que $B$, denotado por $A < B$, si y solo si existe $1 \leq p \leq m$ tal que $a_p < b_p$ y $a_i = b_i$ para todos los $1 \leq i < p$. Además, se define $A \leq B$ si y solo si $A < B$ o $A = B$.

Bobo tiene una matriz $C$ de $n$ filas y $m$ columnas. Quiere encontrar la permutación $\sigma_1, \sigma_2, \dots, \sigma_m$ de $1, 2, \dots, m$ lexicográficamente más pequeña que satisfaga $S_1 \leq S_2 \leq \dots \leq S_n$, donde $S_i = (C_{i, \sigma_1}, C_{i, \sigma_2}, \dots, C_{i, \sigma_m})$.

Entrada

El archivo de entrada contiene varios casos de prueba. Procesa la entrada hasta el final del archivo.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $m$.

Las siguientes $n$ líneas contienen $m$ enteros cada una; la línea $i$ contiene $C_{i, 1}, C_{i, 2}, \dots, C_{i, m}$.

• $1 \leq n, m \leq 2000$
• $1 \leq C_{i, j} \leq 10^9$
• La suma de $n \times m$ no supera $10^7$.

Salida

Para cada caso de prueba, si existe una solución, imprime $m$ enteros que representen la secuencia $\sigma_1, \sigma_2, \dots, \sigma_m$ lexicográficamente más pequeña. En caso contrario, imprime -1.

Ejemplos

Entrada 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

Salida 1

2 1 3
1 2
-1