Se tienen $n$ puntos de datos en un espacio de Manhattan de $d$ dimensiones, todos ubicados sobre los ejes coordenados. La arista entre dos puntos tiene un peso definido como su distancia de Manhattan. Se debe encontrar un emparejamiento perfecto de peso total mínimo. Está garantizado que $n$ es par.

Específicamente, cada punto de datos tiene a lo sumo una coordenada distinta de cero en alguna dimensión. La arista entre dos puntos $u = (u_1, u_2, ..., u_d)$ y $v = (v_1, v_2, ..., v_d)$ se define como $d(u, v) := \sum\limits_{i=1}^d |u_i - v_i|$.

Se deben imprimir $n$ números, que indican para cada punto el número del punto con el que está emparejado. Los puntos se numeran a partir de $1$.

Restricciones

$1 \leq n \leq 10^5$, $1 \leq d \leq 20$

Todas las coordenadas de cada punto son enteros con valor absoluto no mayor a $10^9$.

Entrada

La primera línea contiene dos enteros positivos $n, d$, que indican la cantidad de puntos y la dimensión del espacio. Las siguientes $n$ líneas contienen cada una $d$ números, que representan las coordenadas de un punto.

Salida

Debes imprimir una línea con $n$ números, que indican para cada punto el número del punto con el que está emparejado.

Ejemplos

Entrada 1

10 3
-2 0 0
-1 0 0
0 0 0
1 0 0
2 0 0
0 1 0
0 2 0
0 3 0
0 0 1
0 0 2

Salida 1

2 1 6 5 4 3 8 7 10 9