题目描述

具身智能部在探索未知操作台时，会把若干观测点聚合成候选区域，供后续规划模块逐块检查。本题模拟 K-means 的一轮分配与中心更新，用于观察初始中心在一次迭代后的变化。

给定 n 个样本点和 K 个初始中心，请先用原始中心为每个样本分配最近簇，再按分配结果统一更新各簇中心。输出样本的簇编号，以及更新后的中心坐标。

本题只执行一轮。分配阶段距离相同时取簇编号更小；如果某个簇没有分到任何样本，它的中心保持输入时的位置。

输入格式

• 第一行包含 n d K。
• 接下来 n 行输入样本特征。
• 再接下来 K 行输入初始中心。

输出格式

• 第一行输出 n 个样本的簇编号。
• 后续 K 行输出更新后的中心。

数据范围与约束

• 1 <= K <= n <= 10000
• 1 <= d <= 5

判定规则

使用标准输出比较。浮点结果按题面保留 6 位或 10 位小数；阈值等号、无可行分支和 Tie-break 按下列规则处理。

• 只执行一轮分配和更新。
• 分配阶段使用原始中心，距离相同取簇编号更小。
• 空簇中心保持原位置。

样例

输入样例 1

3 2 2
0 0
2 0
10 0
0 0
10 0

输出样例 1

1 1 2
1.000000 0.000000
10.000000 0.000000

输入样例 2

2 1 2
0
1
0
100

输出样例 2

1 1
0.500000
100.000000

样例解释

样例 1 中前两个样本分到簇 1，第三个样本分到簇 2，因此第一个中心更新为 (1,0)。样例 2 中第二个簇为空，中心保持 100。