Cho $n$ điểm dữ liệu trong không gian Manhattan $d$ chiều, mỗi điểm nằm trên một trục tọa độ (chỉ có một chiều khác $0$), trọng số cạnh giữa hai điểm bất kỳ được định nghĩa là khoảng cách Manhattan của chúng, bạn cần tìm một ghép cặp hoàn hảo có tổng trọng số nhỏ nhất. Đảm bảo $n$ là số chẵn.

Cụ thể, mỗi điểm dữ liệu có tối đa một chiều có tọa độ khác $0$. Trọng số cạnh giữa hai điểm $u = (u_1, u_2, ..., u_d)$ và $v = (v_1, v_2, ..., v_d)$ được định nghĩa là $d(u, v) := \sum\limits_{i=1}^d |u_i - v_i|$.

Bạn cần xuất ra $n$ số, cho biết đỉnh mà mỗi điểm được ghép cặp. Các đỉnh được đánh số từ $1$.

Giới hạn

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

Tọa độ mỗi chiều của tất cả các điểm dữ liệu đều là số nguyên có giá trị tuyệt đối không vượt quá $10^9$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào gồm hai số nguyên dương $n, d$, lần lượt là số lượng điểm dữ liệu và số chiều không gian. $n$ dòng tiếp theo, mỗi dòng chứa $d$ số, biểu diễn tọa độ của một điểm dữ liệu.

Dữ liệu ra

Bạn cần xuất ra một dòng gồm $n$ số, là chỉ số của điểm được ghép cặp với mỗi điểm.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

2 1 6 5 4 3 8 7 10 9