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.


-----Input-----

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-----

Output a single integer — the answer to the problem.


-----Examples-----
Input
10 5
0
21
53
41
53

Output
4

Input
5 5
0
1
2
3
4

Output
-1

Difficulty: interview

Starter code:

Solutions:
p, n = map(int, input().split())
a = [-1 for i in range(p)]
for i in range(n):
    b = int(input())
    if a[b % p] != -1:
        print(i + 1)
        return
    else:
        a[b % p] = b
print(-1)

p, _= list(map(int, input().split()))

used = set()

for i in range(_):
    x = int(input())
    if x%p in used:
        print(i+1)
        return
    else:
        used.add(x%p)
print(-1)


p,n=map(int,input().split())
s=set()
for i in range(n):
    x=int(input())
    if x%p in s:
        print(i+1)
        return
    else:
        s.add(x%p)
print(-1)

p, n = list(map(int, input().split()))
arr = [-1 for i in range(1000)]
for i in range(n):
	x = int(input())
	if arr[x % p] != -1:
		print(i+1)
		return
	else:
		arr[x % p] = x
print(-1)


p, n = [int(x) for x in input().split()]
l = [int(input()) for i in range(n)]

table = [False for i in range(p)]
done = False
for i in range(n):
    if table[l[i]%p]:
        print(i+1)
        done = True
        break
    else:
        table[l[i]%p] = True
if not done:
    print(-1)


x, n = list(map(int, input().split()))
a = [False for i in range(x)]

for i in range(n):
    d = int(input()) % x
    if a[d]:
        print(i + 1)
        break
    a[d] = True
else:
    print(-1)

p, n = map(int,input().split())
s = set()
ex = 0
for i in range(n):
    x = int(input())
    if x%p in s:
        print(i+1)
        ex = 1
        break
    s.add(x%p)
if ex == 0:
    print(-1)

p,n=map(int,input().split())
xlist=[]
for i in range(n):
	xlist.append(int(input()))

remainderlist=[]
for i in range(n):
	if xlist[i]%p not in remainderlist:
		remainderlist.append(xlist[i]%p)
	else:
		print(i+1)
		quit()

print(-1)	

n = list(map(int,input().split(' ')))
arr = []
c = False
for  i in range(n[1]):
	t = int(input())
	if(t % n[0] in arr):
		print(i+1)
		c = True
		break
	else:
		arr.append(t % n[0])
if(c==False):
	print(-1)

s = input()
p = int(s.split()[0])
n = int(s.split()[1])
nn = []
bb = False
for i in range(n):
    a = int(input()) % p
    for b in nn:
        if b == a:
            print(i + 1)
            bb = True
            break
    else:
        nn.append(a)
    if bb:
        break
if not bb:
    print(-1)


    


p,n=map(int,input().split())
x=[0 for i in range(n)]
for i in range(n):
	x[i]=int(input())
was=[0 for i in range(p)]
k=-1
for i in range(n):
	if was[x[i]%p]:
		k=i+1
		break
	else:
		was[x[i]%p]=1
print(k)	

__author__ = 'Adela'


def main():
    p, n = (int(k) for k in input().split())
    full = [False] * p
    for i in range(n):
        xi = int(input())
        mod = xi % p
        if full[mod]:
            print(i+1)
            return
        full[mod] = True

    print(-1)

def __starting_point():
    main()

__starting_point()

p, n = map(int,input().split())
x = []
for i in range(n):
    x.append(int(input()))
pos = []
out = -1
for i in range(n):
    a = x[i] % p
    if a in pos:
        out = (i+1)
        break
    else:
        pos.append(a)
        
if out == -1 :
    print(-1)
else:
    print (out)

# bestwillcui
# Codeforces Problem 1

AkshajK = input("").split()

p = int(AkshajK[0])
n = int(AkshajK[1])

c = 1
asdf = []
l_1 = []
for x in range(p):
    l_1.append(0)

while c <= n:
    s = int(input())
    if l_1[s % p] == 0:
        l_1[s % p] = 1
    else:
        asdf.append(c)
    c += 1
if asdf != []:
    print(asdf[0])
else:
    print(-1)


p, n = tuple(map(int, input().split(' ')))
mods = []
result = -2
finished = False

for i in range(n):
    if finished:
        input()
    else:
        tmp = int(input()) % p
        if tmp in mods:
            result = i
            finished = True
        mods.append(tmp)

print(result + 1)

a=input().split()
p=int(a[0])
n=int(a[1])
h=[]
flag=1
for i in range(p):
  h.append(0)
for i in range(n):
  work=int(input())
  work=work % p
  if h[work] and flag:
    answer=i+1
    flag=0
  h[work]=1
if flag:
  answer=-1
print(answer)

h = []
a = -1
P, N = list(map(int, input().split()))
for i in range(N):
    v = int(input()) % P
    if (v in h) and a == -1:
        a = i + 1
    h.append(v)
print(a)


p, n = map(int, input().split())
x = [int(input()) for i in range(n)]
u = [False] * p
for i in range(min(p + 1, n)):
  if u[x[i] % p]:
    print(i + 1)
    break
  u[x[i] % p] = True
else:
  print(-1)

inp = input().strip().split()
inp = [int(i) for i in inp]

p = inp[0]
n = inp[1]

hashDict = {}
conflict = False
insertion = 0
for i in range(n):
    num = int(input().strip())
    num = num%p
    if num in hashDict:
        if conflict:
            continue
        conflict = True
        insertion = i

    else:
        hashDict[num] = True

if conflict:
    print(insertion+1)
else:
    print("-1")



#!/usr/bin/env python


def main():
    p, n = list(map(int, input().split()))
    table = set()
    for i in range(1, n+1):
        x = int(input())

        if x % p in table:
            print(i)
            return
        else:
            table.add(x % p)

#        print(">", x % p, table)

    print(-1)
    return


def __starting_point():
    main()

__starting_point()

#Dead
import math
sa3=[]
sa2=input().split(' ')
prime=int(sa2[0])
nums=int(sa2[1])
for x in range(nums):
    sa=int(input())
    sa3.append(sa)
sa4=[]
sa9001=0
for element in range(len(sa3)):
    sa5=sa3[element]%prime
    if sa5 in sa4 and sa9001!=1:
        print(element+1)
        sa9001=1
    else:
        sa4.append(sa3[element]%prime)
if sa9001==0:
    print(-1)


import sys
p,n = list(map(int,input().split()))
a = [0] * p;
for i in range(n):
    x = int(input())
    if (a[x % p] != 0):
        print(i + 1)
        return
    else:
        a[x % p] = i + 1;
print(-1)


import sys
import string
from decimal import *
from itertools import *
from math import *

def solve():
    p,n = list(map(int,input().split()))
    x = []
    for i in range(n):
        val = int(input())
        if (val % p) not in x:
            x.append(val % p)
        else :
            print(i+1)
            return 0
    print(-1)
solve();


import sys
import string
from decimal import *
from itertools import *
from math import *

def solve():
    p,n = list(map(int,input().split()))
    x = []
    for i in range(n):
        val = int(input())
        if (val % p) not in x:
            x.append(val % p)
        else :
            print(i+1)
            return 0;
    print(-1)
solve();


def main():
    p, n = [int(i) for i in input().split()]
    
    d = [0 for i in range(p)]
    
    for i in range(n):
        x = int(input()) % p
        if d[x]:
            print(i + 1)
            return
        d[x] = 1
    
    print(-1)


main()