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
#include <bits/stdc++.h>
using namespace std;
string convertTostr(unsigned long long x) {
  stringstream ss;
  ss << x;
  string st;
  st = ss.str();
  return st;
}
unsigned long long convertToint(string y) {
  unsigned long long num;
  stringstream ss(y);
  ss >> num;
  return num;
}
unsigned long long fpow(unsigned long long b, unsigned long long p,
                        unsigned long long m) {
  if (p == 0) return 1;
  if (p == 1) return b % m;
  unsigned long long res = fpow(b, p / 2, m) % m;
  res = (res * res) % m;
  if (p % 2 != 0) res = (res * (b % m)) % m;
  return res;
}
long long gcd(long long a, long long b) {
  while (1) {
    if (b == 0) return a;
    if (a == 0) return b;
    if (a < 0)
      a = a * -1;
    else if (b < 0)
      b *= -1;
    else if (a > b)
      swap(a, b);
    int tmp = a;
    a = b % a;
    b = tmp;
  }
}
long long gcdnum(vector<long long> vec) {
  long long ret = vec[0];
  for (int i = 1; i < vec.size(); i++) {
    ret = gcd(ret, vec[i]);
  }
  return ret;
}
const int MAX = 500;
void toarr(string str, int arr[MAX]) {
  int len = str.size() - 1;
  for (int i = len; i >= 0; i--) {
    arr[len - i] = str[i] - '0';
  }
}
int getlen(int arr[MAX]) {
  for (int i = MAX - 1; i >= 0; i--) {
    if (arr[i] != 0) return i;
  }
  return 0;
}
void product(int n1[MAX], int n2[MAX], int result[MAX]) {
  int len1 = getlen(n1);
  int len2 = getlen(n2);
  if (len1 < len2) return product(n2, n1, result);
  int ind = 0;
  for (int i = 0; i <= len2; i++) {
    int pos = 0;
    for (int j = 0; j <= len1; j++) {
      result[pos + ind] += n1[j] * n2[i];
      if (result[pos + ind] > 9) {
        result[pos + ind + 1] += result[pos + ind] / 10;
        result[pos + ind] = result[pos + ind] % 10;
      }
      pos++;
    }
    ind++;
  }
}
void add(int n1[MAX], int n2[MAX], int result[MAX]) {
  int len1 = getlen(n1);
  int len2 = getlen(n2);
  if (len1 < len2) return add(n2, n1, result);
  int carry = 0;
  for (int i = 0; i < MAX; i++) {
    result[i] = n1[i] + n2[i] + carry;
    carry = result[i] / 10;
    result[i] %= 10;
  }
}
void display(int arr[MAX]) {
  int len = getlen(arr);
  for (int i = len; i >= 0; i--) cout << arr[i];
  cout << endl;
}
void display2(int arr[MAX]) {
  int len = getlen(arr);
  int ind = 0;
  while (arr[ind] == 0) ind++;
  for (int i = ind; i <= len; i++) cout << arr[i];
  cout << endl;
}
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  int n, p;
  int arr[400];
  memset(arr, 0, sizeof arr);
  cin >> p >> n;
  int x;
  int ans = -1;
  for (int i = 0; i < n; i++) {
    cin >> x;
    x = x % p;
    if (arr[x] != 0 && ans == -1) ans = i + 1;
    arr[x] = 1;
  }
  cout << ans;
  return 0;
}
