给定 $d$ 维曼哈顿空间中的 $n$ 个在 坐标轴 上的数据点，任意两点之间的边权定义为他们的 曼哈顿距离，你需要求一个总边权最小的完美匹配。保证 $n$ 是偶数。

具体来说，每个数据点至多只有一维的坐标非 $0$。两点 $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$ 的整数。

输入

输入的第一行为两个正整数 $n, d$，分别表示数据点数量和空间维度。 接下来 $n$ 行，每行 $d$ 个数，表示一个数据点的坐标。

输出

你需要输出一行 $n$ 个数，表示每个点匹配的另一个点编号。

样例输入

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

样例输出

2 1 6 5 4 3 8 7 10 9