题目内容

在个性化推荐系统中，用户的偏好是复杂的。系统不仅知道用户对各项特征（如价格、性能、外观）用户对每个特征的重视程度（权重）。

例如，用户 $A$ 非常看重“价格”（权重高），但不太在意“颜色”（权重低）。 你需要根据目标用户的特征向量 $T$ 和特征权重向量 $W$，从商品库中找出最匹配的 $K$ 个商品。

给定

1. 目标用户的特征向量 $T = [t_1, t_2, \dots, t_D]$。
2. 特征权重向量 $W = [w_1, w_2, \dots, w_D]$。
3. $N$ 个备选商品的特征向量 $I = [i_1, i_2, \dots, i_D]$。

请计算每个商品与目标用户之间的加权欧氏距离平方（Weighted Squared Euclidean Distance），并返回距离最近的 $K$ 个商品ID。

加权距离计算公式：

（即：第 $j$ 个维度的差值的平方，乘以该维度的权重，最后累加）

排序规则

1. Score 越小越好（相似度越高）。
2. 若 $Score$ 相同，则按 商品ID（整数）从小到大 排序。

输入描述

• 第一行包含三个正整数 $N, D, K$（商品数、维度、推荐数）。
• 第二行包含 $D$ 个整数，代表 特征权重向量 $W$。
• 第三行包含 $D$ 个整数，代表 目标用户向量 $T$。
• 接下来的 $N$ 行，每行格式为：
  • 第一个整数为 商品 $ID$，
  • 随后 $D$ 个整数，代表该商品的特征向量。

输出描述

输出一行，包含 $K$ 个整数，表示排名前 $K$ 的商品 $ID$，用空格分隔。

样例1

输入

3 2 2
100 1
10 10
101 10 20
102 12 10
103 10 10

输出

103 101

说明

• 权重 $W = [100, 1]$（非常看重第一个维度，不太看重第二个）。
• 目标 $T = [10, 10]$。
• 商品 $101$ ($[10, 20]$)：
  • 维度 $1$ 差异：$(10 - 10)^2 \times 100 = 0$
  • 维度 $2$ 差异：$(10 - 20)^2 \times 1 = 100$
  • 总分：$100$
• 商品 $102$ ($[12, 10]$)：
  • 维度 $1$ 差异：$(10 - 12)^2 \times 100 = 4 \times 100 = 400$
  • 维度 $2$ 差异：$(10 - 10)^2 \times 1 = 0$
  • 总分：$400$
• 商品 $103$ ($[10, 10]$)：
  • 完全匹配，总分 $0$。

排序：$103(0) < 101(100) < 102(400)$。 输出前 $2$ 名：$103$ $101$