← 返回题目列表

Codeforces · 447/A

A. DZY 喜欢哈希

中文机器翻译题面 查看原题

DZY 有一个包含 p 个桶的哈希表,编号从 0 到 p - 1。他想要按照给出的顺序将 n 个数字插入到哈希表中。对于第 i 个数字 xi,DZY 会将其放入编号为 h(xi) 的桶中,其中 h(x) 是哈希函数。在这个问题中,我们假设 h(x) = x mod p。运算 a mod b 表示 a 除以 b 后取余数。

但是,每个存储桶只能包含一个元素。如果 DZY 想要将一个数字插入到已经填满的桶中,我们就说发生了“冲突”。假设第一次冲突发生在第 i 次插入之后,您应该输出 i。如果没有发生冲突,则输出-1。

输入

第一行包含两个整数 p 和 n (2 ≤ p, n ≤ 300)。然后是n行。其中第 i 个包含整数 xi (0 ≤ xi ≤ 109)。

输出

输出一个整数——问题的答案。

示例

输入 #1

10 5
0
21
53
41
53

输出 #1

4

输入 #2

5 5
0
1
2
3
4

输出 #2

-1