题目内容

在推荐检索系统中，需要对用户向量完成一轮分群更新。给定 $n$ 个用户、$k$ 个当前群中心，以及距离阈值 $T$，按下列规则得到本轮分群结果与更新后的中心。

记用户 $i$ 的特征向量为 $x_i=(x_{i,1},\ldots,x_{i,d})$，群中心 $j$ 为 $c_j=(c_{j,1},\ldots,c_{j,d})$（编号从 $0$ 到 $k-1$），维度权重为 $w_1,\ldots,w_d$。

用户 $i$ 到中心 $j$ 的距离为

按下面步骤处理：

1. 分配：对每个用户 $i$，在所有中心中取使 $d(i,j)$ 最小的编号 $j^*$；若有多个中心距离相同，取编号更小的那个。若 $d(i,j^*)>T$，该用户标记为离群，簇编号记为 $-1$，且不参与任何中心的更新；否则将该用户分入簇 $j^*$。
2. 更新：对每个簇 $j$（$0\le j<k$）：
   • 若本轮没有任何用户分入该簇，则中心 $c_j$ 保持不变；
   • 否则，设该簇内用户集合为 $S_j$，新中心第 $t$ 维为

输出本轮分配得到的簇编号，以及更新后的 $k$ 个中心。

输入描述

第一行四个整数 $n$、$d$、$k$、$T$，用空格分隔，依次表示用户数、特征维数、群中心数与距离阈值。

第二行 $d$ 个正整数 $w_1,\ldots,w_d$，为维度权重。

接下来 $k$ 行，第 $j$ 行给出中心 $j$ 的 $d$ 个整数坐标。

接下来 $n$ 行，第 $i$ 行给出用户 $i$ 的 $d$ 个整数特征。

约束

• $1 \le n \le 200$
• $1 \le d \le 10$
• $1 \le k \le 20$
• $0 \le T \le 10^9$
• $1 \le w_t \le 100$
• 所有坐标的绝对值不超过 $10^6$

输出描述

第一行输出 $n$ 个整数，为每个用户的簇编号（离群为 $-1$），相邻整数之间用一个空格分隔。

接下来 $k$ 行，按编号从 $0$ 到 $k-1$ 输出更新后的中心；每行 $d$ 个整数，相邻整数之间用一个空格分隔。

样例1

输入

4 2 2 10
1 2
0 0
10 10
1 1
2 2
9 9
0 20

输出

0 0 1 -1
1 1
9 9

说明

权重 $w=(1,2)$，阈值 $T=10$。

• 用户 $(1,1)$：到中心 $0$ 为 $1\cdot 1+2\cdot 1=3$，到中心 $1$ 为 $27$，取簇 $0$。
• 用户 $(2,2)$：到中心 $0$ 为 $6$，到中心 $1$ 为 $24$，取簇 $0$。
• 用户 $(9,9)$：到中心 $0$ 为 $27$，到中心 $1$ 为 $3$，取簇 $1$。
• 用户 $(0,20)$：到中心 $0$ 为 $40$，到中心 $1$ 为 $30$，最小距离 $30>10$，记为 $-1$。

簇 $0$ 含 $(1,1),(2,2)$，新中心为 $(\lfloor 3/2\rfloor,\lfloor 3/2\rfloor)=(1,1)$。簇 $1$ 含 $(9,9)$，新中心为 $(9,9)$。

样例2

输入

5 1 3 5
1
0
4
20
2
3
5
1
100

输出

0 1 1 0 -1
1
4
20

说明

用户 $2$ 到中心 $0$ 与中心 $1$ 的距离均为 $2$，取编号更小的簇 $0$。用户 $100$ 的最小距离为 $80>5$，记为 $-1$。簇 $2$ 本轮无人分入，中心保持 $20$。簇 $0$ 含 $\{2,1\}$，新中心为 $\lfloor 3/2\rfloor=1$；簇 $1$ 含 $\{3,5\}$，新中心为 $\lfloor 8/2\rfloor=4$。