$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$개의 수를 출력합니다. $i$번째 수는 $i$번 점이 매칭된 상대 점의 번호입니다.

예제

입력 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