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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

// Note that at the actual CodeForces contest,
// - must use the default package
// - can use any class name
public class CF255Div2A {

	void solve(int p, int n, int[] x) {
		boolean[] hash = new boolean[p];
		Arrays.fill(hash, false);
		int ans = -1;
		for (int i = 0; i < n; i++) {
			int hx = x[i] % p;
			if (hash[hx]) {
				ans = i + 1;
				break;
			} else {
				hash[hx] = true;
			}
		}
		pw.println(ans);
	}

	void solve(InputStream in, PrintStream out) {
		br = new BufferedReader(new InputStreamReader(in));
		pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));
		int p = ni();
		int n = ni();
		int[] x = na(n);
		solve(p, n, x);
		pw.close();
	}

	public static void main(String[] args) {
		new CF255Div2A().solve(System.in, System.out);
	}

	/*
	 *  common codes hereinafter
	 */

	static StringTokenizer st;
	static BufferedReader br;
	static PrintWriter pw;

	String ns() {
		while (st == null || !st.hasMoreTokens())
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
				System.exit(1);
			}
		return st.nextToken();
	}

	int ni() {
		return Integer.parseInt(ns());
	}

	long nl() {
		return Long.parseLong(ns());
	}

	double nd() {
		return Double.parseDouble(ns());
	}

	int[] na(int n) {
		return na(n, 0);
	}

	int[] na(int n, int offset) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = ni() - offset;
		}
		return a;
	}

	int[][] na2(int n, int m) {
		return na2(n, m, 0);
	}

	int[][] na2(int n, int m, int offset) {
		int[][] a = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				a[i][j] = ni() - offset;
			}
		}
		return a;
	}

	boolean[][] nab(int n, int m) {
		boolean[][] a = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			char[] cc = ns().toCharArray();
			for (int j = 0; j < cc.length; j++) {
				a[i][j] = cc[j] == '1';
			}
		}
		return a;
	}
}
