题目内容

模式识别是智能感知系统实现自主决策与环境理解的重要能力，从传感器信号中捕捉周期性与谐波特征是其中的关键环节。本问题要求构建一个基于频域特征的 K-Means 聚类系统，处理过程分为三个步骤。

第一步：离散傅里叶变换。给定 $N$ 组信号 $data[0], data[1], \dots, data[N-1]$，每组信号长度为 $L$。对每组信号 $x[n]$ 计算 DFT：

其中 $k = 0,1,\dots,L-1$。将复数 $X[k]$ 写成 $X[k] = Re[k] + j \cdot Im[k]$，其实部和虚部分别为：

第二步：提取频域峰值特征。对每个频率索引 $k$，定义幅值：

考虑 $k$ 从 1 到 $\lfloor (L-1)/2 \rfloor$ 的频点，即排除直流分量 $k=0$ 以及最高频率分量。按幅值从大到小排序；若幅值相等，则 $k$ 较小的排在前面。取前 3 个最大幅值对应的 $k$ 值，按幅值从大到小的顺序构成一个 3 维特征向量，记为 $feature[i]$。

第三步：K-Means 聚类。聚类数 $K$ 由输入给定。使用欧几里得距离衡量样本与中心的相似度：

初始聚类中心的选取方式：输入给出 $K$ 个整数索引，每个索引指向一个原始信号，将这些信号的特征向量直接作为初始聚类中心。

迭代过程如下：

• 将每个样本分配给欧几里得距离最近的中心。
• 对每个簇，计算簇内所有样本特征向量在每个维度上的均值，并使用银行家舍入规则取整，作为新的中心。
• 若某个簇没有样本，则保留该中心不变。
• 最多迭代 100 次；若所有聚类中心前后两次的变化误差不超过 $10^{-4}$，则提前停止。

银行家舍入规则：

• 当舍去部分首位数字小于 5 时，直接舍去；
• 当舍去部分首位数字大于 5 时，进位；
• 当舍去部分首位数字等于 5 时，若 5 后面存在非零数字则进位；否则看保留位最后一位，偶数则舍去，奇数则进位。

约束条件：

• 信号组数 $N$ 满足 $9 \le N \le 20$。
• 每组信号长度 $L$ 满足 $20 \le L \le 50$。
• 聚类数 $K$ 满足 $2 \le K \le 4$。

输入描述

输入共 $N+2$ 行。

第一行包含 3 个整数 $N$、$L$、$K$，分别表示信号组数、每组信号长度和聚类数。

接下来 $N$ 行，每行包含 $L$ 个浮点数，表示一组信号数据。

最后一行包含 $K$ 个整数，表示初始聚类中心对应的原始信号索引，索引范围为 $0$ 到 $N-1$。

输出描述

输出共 $K$ 行，每行包含 3 个整数，表示一个最终聚类中心的特征向量。所有行按字典序排序：先比较第一个整数，若相同则比较第二个整数，若仍相同则比较第三个整数。每个整数之间用空格分隔，行末没有多余空格。

样例1

输入

9 20 2
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
0 1

输出

1 2 3
1 2 3

说明

所有信号都是常数 1.0，长度为 20。离散傅里叶变换中，只有 $k=0$ 的直流分量有非零幅值，而特征提取只考虑 $k=1$ 到 $\lfloor(20-1)/2\rfloor=9$ 的频点。因此这些频点的幅值平方均为 0，排序时幅值相等，按 $k$ 较小的优先，取出的三个频点索引为 1、2、3，所以每个样本的特征向量都是 $(1,2,3)$。

初始中心两个都指向 $(1,2,3)$。所有样本到两个中心的距离都为 0，分配时全部归入第一个中心，第二个中心为空簇并保持 $(1,2,3)$ 不变。最终两个中心相同，排序后输出两行 1 2 3。

样例2

输入

9 24 3
1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5
1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5
1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5 1.0 0.5 -0.5 -1.0 -0.5 0.5
1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0
1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0
1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0 1.0 0.0 -1.0 0.0
1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5
1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5
1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5 1.0 -0.5 -0.5
0 3 6

输出

4 1 2
6 1 2
8 1 2

说明

对于频率 $m=4$ 的余弦信号，在长度 $L=24$ 下满足整周期条件。其 DFT 在 $k=4$ 处幅值为 12，在 $k=1$ 到 $k=11$ 的其它频点幅值为 0。由于其它频点幅值相同，按 $k$ 较小优先排序，前三个频点索引依次为 4、1、2，对应特征向量 $(4,1,2)$。同理，频率 $m=6$ 和 $m=8$ 的余弦信号分别得到特征向量 $(6,1,2)$ 和 $(8,1,2)$。

初始中心取自第 0、3、6 组信号，分别对应三个频率簇的代表。每个样本与同频率中心的欧几里得距离为 0，与其它中心的距离大于 0，因此聚类结果保持为三个簇。每个簇包含 3 个相同特征向量，更新后的中心仍然分别是 $(4,1,2)$、$(6,1,2)$、$(8,1,2)$。最后按字典序排序，先比较第一维，输出 4 1 2、6 1 2、8 1 2。