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;
template <typename T>
T BigMod(T b, T p, T m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    T s = BigMod(b, p / 2, m);
    return ((s % m) * (s % m)) % m;
  }
  return ((b % m) * (BigMod(b, p - 1, m) % m)) % m;
}
template <typename T>
T POW(T B, T P) {
  if (P == 0) return 1;
  if (P & 1)
    return B * POW(B, P - 1);
  else
    return POW(B, P / 2) * POW(B, P / 2);
}
template <typename T>
T gcd(T a, T b) {
  if (a < 0) return gcd(-a, b);
  if (b < 0) return gcd(a, -b);
  return (b == 0) ? a : gcd(b, a % b);
}
template <typename T>
T lcm(T a, T b) {
  if (a < 0) return lcm(-a, b);
  if (b < 0) return lcm(a, -b);
  return a * (b / gcd(a, b));
}
int b2d(long long n) {
  int decimalNumber = 0, i = 0, remainder;
  while (n != 0) {
    remainder = n % 10;
    n /= 10;
    decimalNumber += remainder * pow(2, i);
    ++i;
  }
  return decimalNumber;
}
vector<long long> decToBinary(int n) {
  vector<long long> binaryNum(12);
  while (n > 0) {
    binaryNum.push_back(n % 2);
    n = n / 2;
  }
  reverse(binaryNum.begin(), binaryNum.end());
  return binaryNum;
}
int toInt(string s) {
  int sm;
  stringstream second(s);
  second >> sm;
  return sm;
}
long long toLlint(string s) {
  long long sm;
  stringstream second(s);
  second >> sm;
  return sm;
}
bool isVowel(char ch) {
  ch = toupper(ch);
  if (ch == 'A' || ch == 'U' || ch == 'I' || ch == 'O' || ch == 'E')
    return true;
  return false;
}
template <class T>
string NTS(T Number) {
  stringstream second;
  second << Number;
  return second.str();
}
bool isprime(int w) {
  if (w == 0) return false;
  if (w == 1) return false;
  int sqrtw = int(sqrt((double)w));
  for (int q = 2; q <= sqrtw; q++) {
    if (w % q == 0) return false;
  }
  return true;
}
int main() {
  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  };
  long long n, m, i = 0;
  cin >> n >> m;
  map<int, int> mp;
  while (m--) {
    long long a;
    cin >> a;
    if (mp[a % n] == 0)
      mp[a % n] = 1;
    else {
      cout << i + 1 << "\n";
      exit(0);
    }
    i++;
  }
  cout << -1 << "\n";
}
