Дано $n$ точек в $d$-мерном манхэттенском пространстве, лежащих на координатных осях. Вес ребра между любыми двумя точками определяется как их манхэттенское расстояние. Требуется найти совершенное паросочетание с минимальным суммарным весом рёбер. Гарантируется, что $n$ чётно.

В частности, у каждой точки не более одной ненулевой координаты. Вес ребра между точками $u = (u_1, u_2, \dots, u_d)$ и $v = (v_1, v_2, \dots, 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$ чисел — номер точки, сопоставленной каждой из точек.

Примеры

Входные данные 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