$d$ 次元マンハッタン空間において、座標軸上にある $n$ 個のデータ点が与えられる。任意の2点間の辺重みはそれらの マンハッタン距離 で定義される。総辺重みが最小となる完全マッチングを求めよ。$n$ は偶数であることが保証される。

具体的には、各データ点は高々1次元の座標のみが $0$ 以外である。2点 $u = (u_1, u_2, ..., u_d)$ と $v = (v_1, v_2, ..., v_d)$ 間の辺重みは $d(u, v) := \sum\limits_{i=1}^d |u_i - v_i|$ で定義される。

各点がマッチングする相手の点の番号を $n$ 個出力せよ。点の番号は $1$ から始まる。

制約

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

すべてのデータ点の各次元の座標は絶対値が $10^9$ を超えない整数である。

入力

入力の最初の行は2つの正整数 $n, d$ であり、データ点の数と空間の次元を表す。続く $n$ 行のそれぞれには $d$ 個の数が与えられ、1つのデータ点の座標を表す。

出力

各点がマッチングする相手の点の番号を空白区切りで $n$ 個出力せよ。

入出力例

入力例 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

出力例 1

2 1 6 5 4 3 8 7 10 9