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 xi, DZY will put it into the bucket numbered h(xi), 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 xi (0 ≤ xi ≤ 109).

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
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main
{

    
    public static void main( String args[] )
    {
    	int p , n ;

        MyScanner sc = new MyScanner();
        p = sc.nextInt();
        n = sc.nextInt();
        
        boolean array[]= new boolean[400];
        
        for( int i = 0 ; i < 400 ; ++i ) array[i] = false;
        
        int ans = 1000 ; 
        
        for( int i = 1 ; i <= n ; ++i ) 
        {
        	int temp = sc.nextInt();
        	if( array[temp%p] )
        		ans = Math.min( ans ,  i );
        	
        	else 
        		array[temp%p]  = true;
        }
        
        if( ans == 1000 )
        	System.out.println( "-1" );
        else 
        	System.out.println( ans );
    
        
    }
    
//-----end of main-------------------------


    
    static int gcd ( int a , int  b)
    {
    	if( a == 0 ) return b;
    	else if( b == 0 ) return a;
    	
    	else
    	{
    		if( a < b )
    			return gcd( b%a , a );
    		
    		else 
    			return gcd( a%b , b );
    		
    	}
    	
    }
//------------------end of  gcd --------------------

 

    static class MyScanner {
          BufferedReader br;
          StringTokenizer st;
    
          public MyScanner() {
             br = new BufferedReader(new InputStreamReader(System.in),8*1024);
          }
    
          String next() {
              while (st == null || !st.hasMoreElements()) {
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (IOException e) {
                      e.printStackTrace();
                  }
              }
              return st.nextToken();
          }
    
          int nextInt() {
              return Integer.parseInt(next());
          }
    
          long nextLong() {
              return Long.parseLong(next());
          }
    
          double nextDouble() {
              return Double.parseDouble(next());
          }
    
          String nextLine(){
              String str = "";
          try {
             str = br.readLine();
          } catch (IOException e) {
             e.printStackTrace();
          }
          return str;
          }

       }
 //----------end of MyScanner---------------------------------
}