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

import static java.lang.Math.*;

public class solver implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void init() throws FileNotFoundException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        //in = new BufferedReader(new FileReader("input.txt"));
        //out = new PrintWriter("output.txt");
    }

    String readString() {
        try {
            while (!tok.hasMoreTokens()) {
                try {
                    tok = new StringTokenizer(in.readLine());
                } catch (Exception e) {
                    return null;
                }
            }
            return tok.nextToken();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    int readInt() {
        return Integer.parseInt(readString());
    }

    long readLong() {
        return Long.parseLong(readString());
    }

    double readDouble() {
        return Double.parseDouble(readString());
    }

    public static void main(String[] args) {
        new Thread(null, new solver(), "", 256 * (1L << 20)).start();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            init();
            solve();
            out.close();
            time();
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }
    
    
    void solve() {
        int p = readInt();
        int n = readInt();
        
        int[] h = new int[p];
        
        Arrays.fill(h, -1);
        
        for (int i=0;i<n;i++) {
            int index = readInt() % p;
            if (h[index]!= -1) {
                out.println(i + 1);
                return;
            }
            h[index] = i;
        }
        out.println(-1);
    }
}