题目内容

某大型企业正在运营一套智能营销平台。平台需要依据已注册客户的购买偏好特征，将客户自动划分为若干群组，以支持后续的商品推荐与精准推广。为了避免不同群组之间人数差异过大，分群过程还必须满足严格的均衡容量限制。

现有 $N$ 位已注册客户，每位客户由 $M$ 个非负整数特征表示。平台需要使用一种 KMeans 变种聚类，将这些客户划分到 $K$ 个群组中。各群组的最终容量已经由 $N$ 和 $K$ 唯一确定：任意两个群组的人数最多相差 $1$，若 $N$ 不能被 $K$ 整除，则额外的名额优先分配给聚类中心编号较小的群组。

设

则编号为 $1$ 到 $r$ 的群组容量为 $q+1$，其余群组容量为 $q$。例如，当 $N=11,\ K=3$ 时，各群组容量依次为 $[4,4,3]$。

初始时，直接取输入中的前 $K$ 位客户特征作为 $K$ 个聚类中心，并按照它们在输入中的先后顺序编号为 $1,2,\ldots,K$。

之后不断执行以下聚类过程：

• 每一轮均按照客户编号从小到大的顺序处理，即严格遵循输入顺序。
• 对当前处理的客户，计算其与全部 $K$ 个当前聚类中心之间的欧几里得距离。
• 将这些中心按照距离从小到大考虑；若多个中心与该客户的距离相同，则中心编号较小者优先。
• 客户应被分配给上述顺序中第一个尚未达到规定容量上限的群组。已经达到本组目标容量的中心不能再接收客户。
• 当本轮所有客户均完成分配后，分别重新计算每个群组的聚类中心。新中心的每一维特征均等于该群组所有成员对应维度特征的算术平均值，并对结果向下取整。
• 若某一轮结束后，所有客户的分组结果以及全部聚类中心均与此前保持不变，则聚类过程终止。

聚类完成后，还需要对最终得到的 $K$ 个中心重新排序。排序采用 字典序（Lexicographical order）升序，之后输出排序后的全部中心。

另外，输入中还包含一位新客户。需要使用已经完成聚类后的最终中心判断其所属群组：计算新客户与全部最终中心之间的欧几里得距离，并选择距离最小的中心；若存在多个距离相同且均为最小值的中心，则选择字典序最小的中心。

新客户最终输出的群组编号，不再使用聚类过程中原有的中心编号，而是使用最终中心经过字典序排序后的位置编号，编号从 $1$ 开始。

欧几里得距离（Euclidean distance）

对于两个 $M$ 维特征向量

它们之间的欧几里得距离定义为

在仅比较距离大小时，可以直接比较对应的平方和而不进行开方，这不会改变距离的大小关系。

均衡分组（Balanced partitioning）

$N$ 位客户必须被划分到 $K$ 个群组中，每组人数只能为

或

若 $N$ 不能被 $K$ 整除，则共有 $N\bmod K$ 个群组需要比其他群组多接收 $1$ 位客户，这些额外名额依次分配给中心编号较小的群组。

因此，各群组人数最多相差 $1$，且人数较多的群组始终对应编号更小的中心。

字典序（Lexicographical order）

对于两个 $M$ 维特征向量，从第 $1$ 维开始依次比较。若当前维度相同，则继续比较下一维；第一个不同维度中数值较小的向量，其字典序更小。

例如：

唯一性规则

为了保证整个分配过程具有唯一结果，每轮处理客户时必须同时遵守以下规则：

• 客户严格按照输入顺序依次进行分配。
• 优先选择与客户距离更近的中心。
• 若距离相同，则优先考虑中心编号更小的中心。
• 若某个中心对应群组已经达到规定容量，则跳过该中心，继续考虑后续可接收该客户的中心。

新客户 KNN 归属

聚类结束后，将新客户与所有最终聚类中心进行距离比较：

• 新客户归属于欧几里得距离最小的中心。
• 如果有多个中心的最小距离相同，则选择其中字典序最小的中心。
• 最终输出的是该中心在字典序排序后的 $K$ 个中心中的位置，位置编号从 $1$ 开始。

输入描述

输入格式

• 第 $1$ 行包含 $3$ 个整数 $N,M,K$，以空格分隔。
• 第 $2$ 行至第 $N+1$ 行，每行包含 $M$ 个非负整数，表示一位已注册客户的特征。
• 第 $N+2$ 行包含 $M$ 个非负整数，表示新客户的特征。

输入参数范围

每一个特征值均满足

输出描述

输出格式

• 前 $K$ 行依次输出最终得到的 $K$ 个聚类中心。每行包含 $M$ 个整数，各中心按照字典序升序排列。
• 第 $K+1$ 行输出新客户归属的中心编号。该编号表示对应中心在字典序排序后的中心序列中的位置，编号从 $1$ 开始。

样例1

输入

5 1 2
0
10
0
10
20
5

输出

6
10
1

说明

输入中 N 为 5，M 为 1，K 为 2。容量计算为 $q=\lfloor 5/2\rfloor=2$，$r=1$，因此编号 0 的群组容量为 3，编号 1 的群组容量为 2。初始中心为前两个客户的特征值 $C_0=0$、$C_1=10$。

第一轮按顺序处理客户。客户 0 值 0 到 $C_0$ 距离平方为 0，分到群组 0；客户 1 值 10 到 $C_1$ 距离平方为 0，分到群组 1；客户 2 值 0 分到群组 0；客户 3 值 10 分到群组 1，此时群组 1 已达到容量 2；客户 4 值 20 到 $C_1$ 距离平方为 100，到 $C_0$ 距离平方为 400，由于群组 1 已满，分到仍有容量的群组 0。

第一轮结束后，群组 0 包含 $\{0,0,20\}$，群组 1 包含 $\{10,10\}$。更新中心：$C_0=\lfloor(0+0+20)/3\rfloor=6$，$C_1=\lfloor(10+10)/2\rfloor=10$。

第二轮分配结果不变，中心仍为 $(6,10)$，达到收敛。最终中心按字典序升序为 6、10。新客户 5 到 6 的距离平方为 1，到 10 的距离平方为 25，因此归属第 1 个中心。

样例2

输入

4 2 2
0 0
0 10
10 0
10 10
5 5

输出

5 0
5 10
1

说明

输入中 N 为 4，M 为 2，K 为 2。容量计算为 $q=\lfloor 4/2\rfloor=2$，$r=0$，两个群组容量都为 2。初始中心为前两个客户：$(0,0)$ 和 $(0,10)$。

第一轮中，客户 $(0,0)$ 到中心 $(0,0)$ 距离平方为 0，分到群组 0；客户 $(0,10)$ 到中心 $(0,10)$ 距离平方为 0，分到群组 1；客户 $(10,0)$ 到中心 $(0,0)$ 的距离平方为 $10^2+0^2=100$，到中心 $(0,10)$ 的距离平方为 $10^2+(-10)^2=200$，因此分到群组 0；客户 $(10,10)$ 到中心 $(0,10)$ 的距离平方为 $10^2+0^2=100$，小于到 $(0,0)$ 的距离平方 $10^2+10^2=200$，因此分到群组 1。

第一轮后，群组 0 为 $(0,0),(10,0)$，中心更新为 $(\lfloor(0+10)/2\rfloor,\lfloor(0+0)/2\rfloor)=(5,0)$；群组 1 为 $(0,10),(10,10)$，中心更新为 $(\lfloor(0+10)/2\rfloor,\lfloor(10+10)/2\rfloor)=(5,10)$。

第二轮分配与第一轮相同，中心不变，达到收敛。最终中心按字典序升序为 $(5,0)$ 和 $(5,10)$。新客户 $(5,5)$ 到两个中心的距离平方都是 25，并列时选择字典序位置更靠前的 $(5,0)$，对应第 1 个中心。

样例3

输入

2 1 2
7
3
4

输出

3
7
1

说明

输入中 N 为 2，M 为 1，K 为 2。这是一个最小规模的边界情况，容量计算为 $q=\lfloor 2/2\rfloor=1$，$r=0$，两个群组容量都为 1。初始中心为前两个客户的特征值 $7$ 和 $3$。

第一轮中，客户 7 到中心 $7$ 的距离平方为 0，到中心 $3$ 的距离平方为 16，分到群组 0；客户 3 到中心 $3$ 的距离平方为 0，分到群组 1。更新后的中心仍为 $7$ 和 $3$。

下一轮分配结果与中心都不变，达到收敛。最终中心按字典序升序输出，一维向量的字典序即为数值大小，因此先输出 3，再输出 7。新客户 4 到 3 的距离平方为 1，到 7 的距离平方为 9，因此归属排序后的第 1 个中心。