DZY Loves Hash

题目描述 zyk正在学哈希，将某个数字通过取模运算，存储到相应位置。具体做法，设置一个存储位置长度p，对于一个数字xi，xi将存放在xi mod p 位置，如：p=3， xi=14，那么xi将存放在 14 mod 3 = 2的位置。 然而，这样的哈希肯定会存在冲突，比如p=3， x1=14经过哈希后要放在2位置， x2=5经过哈希后也要放在2位置，那么就存在冲突了。 现在给你整数p以及n，然后输入n个整数xi，如果第一个冲突的数字是xi，那么就输出i，然后结束。如果没有冲突，就输出-1。 输入 输入p, n 然后n行每行输入xi 输出 输出相应答案 样例输入 10 5 0 21 53 41 53 样例输出 4 提示 【样例说明】 41 mod 10 = 21 mod 10 【数据规模和约定】 2<= p, n <=300 0<= xi <= 10^9

DZY has a hash table with $ p $ buckets, numbered from $ 0 $ to $ p-1 $ . He wants to insert $ n $ numbers, in the order they are given, into the hash table. For the $ i $ -th number $ x_{i} $ , DZY will put it into the bucket numbered $ h(x_{i}) $ , where $ h(x) $ is the hash function. In this problem we will assume, that $ h(x)=x mod p $ . Operation $ a mod b $ denotes taking a remainder after division $ a $ by $ b $ . However, each bucket can contain no more than one element. If DZY wants to insert an number into a bucket which is already filled, we say a "conflict" happens. Suppose the first conflict happens right after the $ i $ -th insertion, you should output $ i $ . If no conflict happens, just output -1.

The first line contains two integers, $ p $ and $ n $ $ (2<=p,n<=300) $ . Then $ n $ lines follow. The $ i $ -th of them contains an integer $ x_{i} $ $ (0<=x_{i}<=10^{9}) $ .

Output a single integer — the answer to the problem.

10 5
0
21
53
41
53

4

5 5
0
1
2
3
4

-1