Étant donné $n$ points de données situés sur les axes dans un espace de Manhattan à $d$ dimensions, le poids d'une arête entre deux points quelconques est défini comme leur distance de Manhattan. Vous devez trouver un couplage parfait de poids total minimal. Il est garanti que $n$ est pair.

Plus précisément, chaque point de données a au plus une coordonnée non nulle. Le poids d'une arête entre deux points $u = (u_1, u_2, ..., u_d)$ et $v = (v_1, v_2, ..., v_d)$ est défini par $d(u, v) := \sum\limits_{i=1}^d |u_i - v_i|$.

Vous devez afficher $n$ entiers, indiquant le numéro de l'autre point auquel chaque point est jumelé. Les points sont numérotés à partir de $1$.

Entrée

La première ligne de l'entrée contient deux entiers positifs $n$ et $d$, respectivement le nombre de points et la dimension de l'espace. Les $n$ lignes suivantes contiennent chacune $d$ entiers, représentant les coordonnées d'un point de données.

Sortie

Vous devez afficher une ligne contenant $n$ entiers, indiquant le numéro de l'autre point jumelé à chaque point.

Exemples

Entrée 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

Sortie 1

2 1 6 5 4 3 8 7 10 9

Contraintes

$1 \leq n \leq 10^5$, $1 \leq d \leq 20$. Toutes les coordonnées des points sont des entiers dont la valeur absolue ne dépasse pas $10^9$.