题目内容

在智能农业系统中，需要根据作物的多项生长指标（例如高度、叶片数、颜色分量等）来判断作物品种。现已有一批已标注品种的参考样本数据，需要编写程序对一株待判断的作物进行分类。

分类规则采用最近邻投票策略：查找特征空间中与待判断作物距离最近的 3 个参考样本，根据它们的品种标签进行投票。如果得票最多的品种唯一，则将该品种作为输出；若有多个品种得票数并列最高，则比较这 3 个样本中对应品种的距离之和，选择距离之和最小的品种作为最终分类结果。距离采用欧几里得距离。

约束：参考样本的个数 $n$ 满足 $1 \le n \le 10^4$，每个样本的特征维度 $m$ 满足 $1 \le m \le 100$，所有坐标值的绝对值不超过 $10^3$。

输入描述

输入共三行。 第一行包含一个二维列表，表示参考样本的特征数据，其中每个元素是一个实数列表，所有列表的长度相同。 第二行包含一个一维列表，表示每个参考样本对应的品种标签（整数）。 第三行包含一个一维列表，表示待分类作物的特征数据，其长度与参考样本的特征维度相同。 所有输入均可用 eval() 直接解析为 Python 列表。

输出描述

输出一个整数，表示预测的品种标签。

样例1

输入

[[0,0],[1,0],[0,1]]
[1,2,2]
[0,0.1]

输出

2

说明

待分类点 [0, 0.1] 与三个参考点的欧几里得距离：到 [0,0] 为 0.1，到 [1,0] 为 $\sqrt{(1-0)^2+(0-0.1)^2} \approx 1.005$，到 [0,1] 为 0.9。最近的 3 个邻居（即全部样本）的标签依次为 1、2、2。其中标签 2 出现 2 次，标签 1 出现 1 次，得票最多的标签为 2，故输出 2。

样例2

输入

[[0,0],[1,0],[0,1],[10,10]]
[1,2,3,4]
[0.1,0.1]

输出

1

说明

计算待分类点 [0.1, 0.1] 到各参考点的距离：到 [0,0] 约为 $\sqrt{0.1^2+0.1^2} \approx 0.141$，到 [1,0] 约为 $\sqrt{0.9^2+0.1^2} \approx 0.906$，到 [0,1] 约为 $\sqrt{0.1^2+0.9^2} \approx 0.906$，到 [10,10] 很远。最近 3 个邻居为 [0,0]、[1,0]、[0,1]，对应标签 1、2、3。这三个标签均出现 1 次，得票数并列最高。此时比较各类别的距离之和：标签 1 距离和为 0.141，标签 2 距离和为 0.906，标签 3 距离和为 0.906。标签 1 的距离和最小，因此输出 1。

样例3

输入

[[1],[5],[10]]
[0,1,0]
[4]

输出

0

说明

特征维度为 1，待分类点 [4] 到三个参考点的距离分别为：到 [1] 为 3，到 [5] 为 1，到 [10] 为 6。最近的 3 个邻居（全部）的标签为 0、1、0。标签 0 出现 2 次，标签 1 出现 1 次，得票最多的标签为 0，输出 0。