Danych jest $n$ punktów w $d$-wymiarowej przestrzeni Manhattanu, leżących na osiach współrzędnych. Waga krawędzi między dowolnymi dwoma punktami jest zdefiniowana jako ich odległość Manhattanu. Należy znaleźć skojarzenie doskonałe o minimalnej sumie wag. Gwarantowane, że $n$ jest parzyste.

Dokładniej, każdy punkt ma co najwyżej jedną współrzędną niezerową. Waga krawędzi między punktami $u = (u_1, u_2, \ldots, u_d)$ i $v = (v_1, v_2, \ldots, v_d)$ jest zdefiniowana jako $d(u, v) := \sum_{i=1}^d |u_i - v_i|$.

Należy wypisać $n$ liczb – dla każdego punktu (w kolejności od $1$ do $n$) indeks punktu, z którym jest skojarzony. Punkty są numerowane od $1$.

Ograniczenia:
$1 \le n \le 10^5$, $1 \le d \le 20$
Wszystkie współrzędne punktów są liczbami całkowitymi, których wartość bezwzględna nie przekracza $10^9$.

Wejście

Pierwszy wiersz wejścia zawiera dwie dodatnie liczby całkowite $n$ i $d$, odpowiednio liczbę punktów i wymiar przestrzeni.
Następne $n$ wierszy zawiera po $d$ liczb całkowitych – współrzędne kolejnych punktów.

Wyjście

Należy wypisać jeden wiersz zawierający $n$ liczb całkowitych – dla każdego punktu (w kolejności od $1$ do $n$) indeks punktu, z którym jest skojarzony.

Przykład

Wejście 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

Wyjście 1

2 1 6 5 4 3 8 7 10 9