题目背景

在疫情期间组织 AMPPZ 是一项很大的挑战。作为“保持社交距离”工作的负责人，你需要确保参赛者之间保持安全距离。

来自同一所大学的学生几乎可以看成一个小团体，因此你主要关心的是不同大学的学生之间的距离。直观地说，你希望同一所大学的学生尽量聚在一起，而不同大学的学生团体之间保持足够远的距离。

为了形式化这个要求，定义：

• $A$：同一所大学内部任意两名学生之间的最大欧几里得距离；
• $B$：不同大学的两名学生之间的最小欧几里得距离。

要求必须满足：

$$A < B$$

比赛期间，所有参赛者都遵守了这个规则。

但是比赛结束之后，大家都已经离开了现场。现在你只拿到了一张从空中拍摄的合影照片，照片中记录了所有学生在平面上的位置，但你并不知道每名学生属于哪一所大学。

幸运的是，你知道当时的分组一定满足上述社交距离规则。现在请你根据所有学生的位置，以及大学数量 $k$，恢复出一种合法的大学划分方案。

题目保证至少存在一种合法方案。

---

题目描述

给定平面上 $n$ 个点，表示 $n$ 名学生的位置。你还知道这些学生来自 $k$ 所大学。

请你为每名学生指定一个大学编号 $c_i$，满足：

$$1 \le c_i \le k$$

并且每一所大学至少有一名学生。

设：

• $A$ 为所有满足 $c_i=c_j$ 的点对 $(i,j)$ 之间欧几里得距离的最大值；
• $B$ 为所有满足 $c_i\ne c_j$ 的点对 $(i,j)$ 之间欧几里得距离的最小值。

你的输出必须满足：

$$A < B$$

如果存在多种合法划分，输出任意一种即可。

---

输入格式

第一行包含一个整数 $z$，表示测试用例组数。

接下来依次给出 $z$ 组测试用例。

每组测试用例的第一行包含两个整数：

$$n,\ k$$

分别表示学生数量和大学数量。

接下来 $n$ 行，每行包含两个整数：

$$x_i,\ y_i$$

表示第 $i$ 名学生在平面上的坐标。

输入中保证没有两名学生站在完全相同的位置。

---

输出格式

对于每组测试用例，输出一行 $n$ 个整数：

$$c_1,\ c_2,\ldots,c_n$$

其中 $c_i$ 表示第 $i$ 名学生所属大学的编号。

必须满足：

$$1 \le c_i \le k$$

并且每个编号 $1,2,\ldots,k$ 都至少出现一次。

如果存在多种合法答案，输出任意一种即可。

---

数据范围

对于每组测试用例：

$$2 \le n \le 2\,000\,000$$ $$2 \le k \le \min(n,20)$$ $$0 \le x_i,y_i < 10^9$$

输入保证：

• 同一组测试用例中，没有两个点坐标完全相同；
• 每组测试用例至少存在一种合法划分方案。

本题当前评测数据由原官方大测试文件按完整测试用例拆分得到。
因此，每个测试用例自身仍满足上述原题限制；每个输入文件中的测试用例数量和总点数以实际数据文件为准，并且不会把单个测试用例拆开。

---

样例输入

3
3 2
0 0
0 1
0 3
4 4
0 0
0 1
1 0
1 1
8 3
3 1
4 1
1 6
2 6
6 5
6 7
3 2
4 2

样例输出

1 1 2
4 1 3 2
2 2 1 1 3 3 2 2

---

样例解释

第一组样例

有 $3$ 名学生、$2$ 所大学。三个点分别为：

$$(0,0),\ (0,1),\ (0,3)$$

一种合法划分是：

$$1,\ 1,\ 2$$

也就是前两名学生属于大学 $1$，第三名学生属于大学 $2$。

此时同一大学内部最大距离为：

$$A=1$$

不同大学之间最小距离为：

$$B=2$$

因此：

$$A < B$$

划分合法。

---

第二组样例

有 $4$ 个点，且 $k=4$。每个学生单独属于一所大学即可。
这样同一所大学内部没有两名不同学生，显然可以满足要求。

样例输出：

$$4,\ 1,\ 3,\ 2$$

只是其中一种合法编号方式。

---

第三组样例

一种合法划分为：

$$2,\ 2,\ 1,\ 1,\ 3,\ 3,\ 2,\ 2$$

这表示学生被划分为三个团体。可以验证，同一团体内部的最远距离严格小于不同团体之间的最近距离，因此满足题目要求。

---

评测说明

本题是 Special Judge 题。
只要输出任意一种满足条件的合法划分，即可判定为正确。
不同合法答案之间的大学编号可以不同，例如把所有编号 $1$ 和 $2$ 互换，仍然是同一个有效划分。