题目内容

在自动驾驶感知系统中，激光雷达会扫描周围环境生成大量3D点云数据，每个点包含 $x$，$y$，$z$ 3D空间坐标。为识别车辆、行人、路障等潜在障碍物，需要先对点云数据做聚类，将属于同一障碍物的点划分为同一个簇。

K-Means是常用的无监督聚类算法，核心是按空间距离分组。预先指定分组数 $K$，先选 $K$ 个初始中心（质心），反复执行两步：

1. 将每个点分配到最近的质心簇中；
2. 用簇内所有点的坐标均值更新质心，直到质心无变化或达到最大迭代次数，完成 $K$ 组聚类。

请实现K-Means聚类算法，将输入的点云数据划分为 $K$ 个簇。要求如下：

1. 初始质心选择：直接使用输入数据的前 $K$ 个点作为初始质心，对应编号 $0$ 到 $K-1$。
2. 距离度量：使用3D欧氏距离，两点 $P(x_1,y_1,z_1)$、$Q(x_2,y_2,z_2)$ 的距离公式为
   $d(P,Q)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$
3. 收敛条件：所有质心的坐标变化量均小于 $10^{-6}$，或迭代次数达到 $100$ 次时停止。
4. 编号保持：迭代过程中，簇编号必须与初始质心的对应关系保持一致。
5. 确定性规则：为保证结果唯一，当一个点到多个质心的距离完全相等时，需选择编号最小的那个簇。

输入描述

第一行：两个整数 $N$（点的数量，$1 \le N \le 1000$）和 $K$（簇的数量，$1 \le K \le N$），空格分隔。

后续 $N$ 行：每行三个浮点数 $x,y,z$，表示3D坐标，范围 $[-100,100]$。

输出描述

输出 $N$ 行，每行一个整数（范围 $0$ 到 $K-1$），代表第 $i$ 个输入点所属的簇编号。

样例1

输入：

3 2
0.0 0.0 0.0
0.0 1.0 1.0
1.0 1.0 0.0

输出：

0
1
0

解释：初始质心为第0个点 $(0.0,0.0,0.0)$（编号0）和第1个点 $(0.0,1.0,1.0)$（编号1）。

第2个点 $(1.0,1.0,0.0)$ 到质心0和质心1的距离均为 $1.41$。根据“距离相等选小编号”规则，被分配到簇0。

样例2

输入：

3 2
0.0 0.0 0.0
2.0 2.0 2.0
0.0 1.0 0.5

输出：

0
1
0

解释：初始质心为第0个点 $(0.0,0.0,0.0)$（编号0）和第1个点 $(2.0,2.0,2.0)$（编号1）。

第2个点 $(0.0,1.0,0.5)$ 到质心0的距离约为 $1.12$，到质心1的距离约为 $2.69$，因此被分配到簇0。