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.Arrays;
import java.util.*;
import java.util.StringTokenizer;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    PrintWriter out;
    BufferedReader input;

    Main() {
        try {
            input = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter(new FileWriter("output.txt"), true);
            solver();
        } catch (Exception ex) {
            ex.printStackTrace();
            input = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out, true);
            solver();
        } finally {
            out.close();
            try {
                input.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    StringTokenizer st = new StringTokenizer("");

    private String nextToken() {
        while (!st.hasMoreElements()) {
            try {
                st = new StringTokenizer(input.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    private int nextInt() {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() {
        return Double.parseDouble(nextToken());
    }

    void solver() {
        int p = nextInt();
        int m = nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            int d = nextInt() % p;
            if (set.contains(d)) {
                out.print(i+1);
                out.close();
                System.exit(0);
            }
            set.add(d);
        }
        out.print(-1);
    }

    public static void main(String[] args) {
        new Main();
    }

}