题目描述

视觉模型会把当前目标和候选物体编码成同维度向量。为了让机器人从候选中找出最像目标的物体，自动化科协具身智能部采用余弦相似度进行匹配。

给定查询向量 q 和 n 个候选向量，请计算每个有效候选与查询向量的余弦相似度，输出相似度最大的候选编号。查询向量或候选向量的范数过小时按无效处理。

输入格式

• 第一行包含两个整数 n、d。
• 第二行包含 d 个浮点数，表示查询向量 q。
• 接下来 n 行每行包含 d 个浮点数，表示第 i 个候选向量，编号为 1..n。

输出格式

• 输出一个整数，表示余弦相似度最大的有效候选编号。
• 若查询向量范数不大于 1e-12，或所有候选向量范数都不大于 1e-12，输出 -1。

数据范围与约束

• 1 <= n <= 10000
• 1 <= d <= 1000
• n*d <= 200000

判定规则

使用标准输出比较。向量有效性和相似度并列按下列规则处理。

• 余弦相似度可以为负数，负相似度候选仍参与比较。
• 候选向量范数不大于 1e-12 时跳过。
• 相似度差不超过 1e-12 时，输出编号更小者。

样例

输入样例 1

2 2
1 0
0 1
2 0

输出样例 1

2

输入样例 2

2 2
0 0
1 0
0 1

输出样例 2

-1

样例解释

样例覆盖零查询、零候选、负相似度和相似度并列。