在疫情期间组织 AMPPZ 是一项巨大的挑战。作为社交距离的首席裁判，你的工作是确保参与者之间保持安全距离。由于来自同一所大学的学生实际上就像一家人，你主要关心的是来自不同大学的学生对之间的距离。直观地说，你希望来自同一所大学的学生组成一个紧密的群体，并与其他所有此类群体保持安全距离。

为了使你的直觉形式化，你提出了以下规则：令 $A$ 表示同一所大学的两名学生之间的最大欧几里得距离（平面上的标准距离），令 $B$ 表示不同大学的两名学生之间的最小欧几里得距离。那么你的规则要求必须满足 $A < B$。

所有的客人都接受了这些指导方针，并在整个活动中遵守了它们。然而，有一个问题：比赛结束后，你被要求证明社交距离规则确实得到了遵守。每个人都已经离开了，唯一剩下的就是尝试使用其中一张合影作为证据……问题是，你不知道哪些参赛者属于哪所大学！但既然你知道社交距离规则得到了遵守，也许你可以恢复大学的分组？

已知照片中所有学生的位置（描述为平面上的点$^1$）和大学的数量，请将学生划分到各所大学中，以满足你的社交距离规则。每所大学必须至少有一名学生；此外，你可以假设解总是存在的。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \leqslant z \leqslant 100\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$ ($2 \leqslant n \leqslant 2\,000\,000, 2 \leqslant k \leqslant \min(n, 20)$)，分别表示学生人数和大学数量。

接下来的 $n$ 行描述了学生的位置。每行包含两个整数 $x_i, y_i$ ($0 \leqslant x_i, y_i < 10^9$)，表示第 $i$ 名学生的坐标。没有两名学生站在完全相同的位置。

所有测试用例的学生总数不超过 $10^7$。

输出格式

对于每个测试用例，输出 $n$ 个整数 $c_1, \dots, c_n$ ($1 \leqslant c_i \leqslant k$)：一种满足社交距离规则的学生大学划分方案。如果存在多种解，你可以输出其中任意一种。

$^1$ 合影是从上方使用无人机拍摄的，因为这是参赛者看起来效果最好的角度。

样例

输入 1

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 1 2
4 1 3 2
2 2 1 1 3 3 2 2

说明

免责声明：样例输入中的空行是为了提高可读性而添加的。它们在真实的输入文件中并不存在。

下面我们展示了样例测试用例以及可能的正确答案。