Có \(N\) điểm trong không gian hai chiều, điểm thứ \(i\) có tọa độ là \((x_i, y_i)\). Có \(M\) loại nguyên tử phóng xạ được đánh số từ \(1\) đến \(M\).

Các nhà khoa học muốn đặt các nguyên tử vào \(N\) điểm, mỗi điểm một loại nguyên tử phóng xạ sao cho độ ổn định là lớn nhất. Độ ổn định của một cách đặt được thể hiện bằng khoảng cách Euclid nhỏ nhất giữa hai nguyên tử phóng xạ cùng loại.

Nhắc lại: khoảng cách Euclid giữa hai điểm \((x_1, y_1)\) và \((x_2, y_2)\) là:

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, M\) \((N \leq 1000, M \leq 5)\)
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i, y_i\) \((|x_i|, |y_i| \leq 10^6)\) thể hiện tọa độ của điểm thứ \(i\)

Output

• Ghi ra trên một dòng \(N\) số nguyên dương, số thứ \(i\) thể hiện loại của nguyên tử được đặt tại điểm \(i\)

Example

5 3
1 0
2 0
3 0
4 0
5 0

1 2 3 1 2

4 2
0 5
5 0
5 5
0 0

1 1 2 2

Scoring

• Subtask 1 (25% số điểm): \(N \leq 10\)
• Subtask 2 (25% số điểm): \(M = 2\)
• Subtask 3 (25% số điểm): \(\forall 1 \leq i \leq n, y_i = 0\)
• Subtask 4 (25% số điểm): không có ràng buộc nào thêm