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.util.*;

/**
 * @author Mukesh Singh
 *
 */
public class Table {

    private InputStream input;
    private PrintStream output;
    private Scanner inputSc;

    public Table(InputStream input, PrintStream output) {
        this.input = input;
        this.output = output;
        init();
    }

    private void init() {
        inputSc = new Scanner(input);
    }

    static int lineToInt(String line) {
        return Integer.parseInt(line);
    }

    static long lineToLong(String line) {
        return Long.parseLong(line);
    }
    static double lineToDouble(String line) {
        return Double.parseDouble(line);
    }


    public void solve() 
	{
            solveTestCase();
    }

/**
 * @define global / instance variables 
 */

	static int val ;
	int mat[][] ;
	int vec[] ;


/**
 * @solve test case 
 */

    private void solveTestCase() 
	{
		int i , j , k , N , M ;
        String str = inputSc.nextLine();
        String delims = "[ ]+";
		String[] tokens = str.split(delims);    
		int p = lineToInt(tokens[0]);
		int ar[] = new int[p] ;
		N = lineToInt(tokens[1]);
		for( i = 0 ; i < N ; i ++ )
		{
        	str = inputSc.nextLine();
			tokens = str.split(delims);    
			M = lineToInt(tokens[0]);
			if(ar[M%p]==1){
				output.println(i+1);
			        return;}
			ar[M%p]=1 ;
		}
		output.println(-1);
    }


    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) 
	{
		FileInputStream in = null;
      	FileOutputStream out = null;
		PrintStream ps = null ;
		InputStream is = null ;
		try 
		{
         	is = new FileInputStream("file.in");
         	out = new FileOutputStream("file.out");
			ps = new PrintStream(out);
        }
		catch ( Exception e )
		{}

        Table sd = new Table(System.in, System.out);
        sd.solve();
		try
		{
        if (is != null) 
		{
	      is.close();
	    }
       	if (out != null) {
           	out.close();
       	}
		if (ps != null) {
           	ps.close();
         }
      	}catch (Exception e){}

		//SquareDetector sd = new SquareDetector(System.in, System.out);
        //sd.solve();
    }
}

