#include <bits/stdc++.h>
using namespace std;
const long long UNDEF = -1;
const int INF = 1 << 30;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
static char stdinBuffer[1024];
static char* stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char* stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
const int MAXN = 1e6 + 4;
const int MAXP = MAXN;
bool sieve_array[MAXP + 1];
int sp[MAXP + 1];
vector<int> gpv;
void sieve() {
  for (int i = 0; i <= MAXP; i++) {
    sieve_array[i] = true;
    sp[i] = INF;
  }
  sieve_array[0] = false;
  sieve_array[1] = false;
  int lim = sqrt(MAXP) + 1;
  for (int i = 2; i <= lim; i++) {
    if (sieve_array[i]) {
      for (int j = i * i; j <= MAXP; j += i) {
        sieve_array[j] = false;
        chkmin(sp[j], i);
      }
    }
  }
  for (int i = 2; i <= MAXP; i++) {
    if (sieve_array[i]) {
      gpv.push_back(i);
      chkmin(sp[i], i);
    }
  }
}
const int mn = 5004;
int a[mn];
int n, k;
const int mx = 1e6 + 4;
int mid[mx];
void f(int m) {
  int have = 0;
  for (int i = 0; i < n; i++) {
    int x = a[i];
    if (x >= m) x %= m;
    if (mid[x] != m) {
      mid[x] = m;
    } else {
      if (have >= k) return;
      ++have;
    }
  }
  printf("%d\n", m);
  exit(0);
}
int target[5000];
int getfac(int x) {
  int sz = 1;
  target[0] = 1;
  while (x > 1) {
    int p = sp[x];
    x /= p;
    int elim = 1;
    while (0 == x % p) {
      x /= p;
      elim++;
    }
    int pp = 1;
    int psz = sz;
    for (int e = 1; e <= elim; e++) {
      pp *= p;
      for (int i = 0; i < psz; i++) {
        target[sz++] = target[i] * pp;
      }
    }
  }
  return sz;
}
const int MK = 10;
const int OVF = 1 << 30;
typedef struct LimitedSetStruct {
  int a[MK];
  int sz;
  void ins(int val) {
    if (sz >= MK) {
      sz = OVF;
      return;
    } else {
      for (int i = 0; i < sz; i++) {
        if (a[i] == val) return;
      }
      a[sz++] = val;
    }
  }
  bool ovf() { return sz == OVF; }
  void setovf() { sz = OVF; }
} LimitedSet;
int ufp[mx];
int ufs[mx];
void ufinit(int n) {
  for (int x = 0; x < n; x++) {
    ufp[x] = x;
    ufs[x] = 1;
  }
}
int uffind(int x) {
  if (ufp[x] != x) {
    ufp[x] = uffind(ufp[x]);
  }
  return ufp[x];
}
void ufunion(int x, int y) {
  if (rand() & 1) swap(x, y);
  int xr = uffind(x);
  int yr = uffind(y);
  if (xr == yr) return;
  ufp[xr] = yr;
  ufs[yr] += ufs[xr];
}
LimitedSet tmp[mx], cand[mx];
int seen[mx];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve();
  n = rint(), k = rint();
  for (int i = 0; i < n; i++) a[i] = rint();
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < x; y++) {
      int diff = abs(a[x] - a[y]);
      if (diff) {
        tmp[diff].ins((x << 16) | y);
      }
    }
  }
  for (int diff = 1; diff < mx; diff++) {
    if (tmp[diff].sz) {
      int sz = getfac(diff);
      for (int i = 0; i < sz; i++) {
        int t = target[i];
        if (tmp[diff].ovf())
          cand[t].setovf();
        else {
          for (int q = 0; q < tmp[diff].sz; q++) {
            cand[t].ins(tmp[diff].a[q]);
          }
        }
      }
    }
  }
  ufinit(mx);
  for (int id = 1; id < mx; id++) {
    if (cand[id].ovf()) continue;
    for (int q = 0; q < cand[id].sz; q++) {
      auto edge = cand[id].a[q];
      int x = edge >> 16, y = edge & 0xffff;
      ufunion(x, y);
    }
    int need = 0;
    for (int q = 0; q < cand[id].sz; q++) {
      auto edge = cand[id].a[q];
      int x = edge >> 16, y = edge & 0xffff;
      if (ufp[x] == x) {
        need += ufs[x] - 1;
        ufs[x] = 1;
      }
      if (ufp[y] == y) {
        need += ufs[y] - 1;
        ufs[y] = 1;
      }
    }
    if (need <= k) {
      printf("%d\n", id);
      return 0;
    }
    for (int q = 0; q < cand[id].sz; q++) {
      auto edge = cand[id].a[q];
      int x = edge >> 16, y = edge & 0xffff;
      ufp[x] = x;
      ufs[x] = 1;
      ufp[y] = y;
      ufs[y] = 1;
    }
  }
}

### Prompt

Construct a Cpp code solution to the problem outlined:

You have been given n distinct integers a1, a2, ..., an. You can remove at most k of them. Find the minimum modular m (m > 0), so that for every pair of the remaining integers (ai, aj), the following unequality holds: <image>.

Input

The first line contains two integers n and k (1 ≤ n ≤ 5000, 0 ≤ k ≤ 4), which we have mentioned above. 

The second line contains n distinct integers a1, a2, ..., an (0 ≤ ai ≤ 106).

Output

Print a single positive integer — the minimum m.

Examples

Input

7 0
0 2 3 6 7 12 18


Output

13


Input

7 1
0 2 3 6 7 12 18


Output

7

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long UNDEF = -1;
const int INF = 1 << 30;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
static char stdinBuffer[1024];
static char* stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char* stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
const int MAXN = 1e6 + 4;
const int MAXP = MAXN;
bool sieve_array[MAXP + 1];
int sp[MAXP + 1];
vector<int> gpv;
void sieve() {
  for (int i = 0; i <= MAXP; i++) {
    sieve_array[i] = true;
    sp[i] = INF;
  }
  sieve_array[0] = false;
  sieve_array[1] = false;
  int lim = sqrt(MAXP) + 1;
  for (int i = 2; i <= lim; i++) {
    if (sieve_array[i]) {
      for (int j = i * i; j <= MAXP; j += i) {
        sieve_array[j] = false;
        chkmin(sp[j], i);
      }
    }
  }
  for (int i = 2; i <= MAXP; i++) {
    if (sieve_array[i]) {
      gpv.push_back(i);
      chkmin(sp[i], i);
    }
  }
}
const int mn = 5004;
int a[mn];
int n, k;
const int mx = 1e6 + 4;
int mid[mx];
void f(int m) {
  int have = 0;
  for (int i = 0; i < n; i++) {
    int x = a[i];
    if (x >= m) x %= m;
    if (mid[x] != m) {
      mid[x] = m;
    } else {
      if (have >= k) return;
      ++have;
    }
  }
  printf("%d\n", m);
  exit(0);
}
int target[5000];
int getfac(int x) {
  int sz = 1;
  target[0] = 1;
  while (x > 1) {
    int p = sp[x];
    x /= p;
    int elim = 1;
    while (0 == x % p) {
      x /= p;
      elim++;
    }
    int pp = 1;
    int psz = sz;
    for (int e = 1; e <= elim; e++) {
      pp *= p;
      for (int i = 0; i < psz; i++) {
        target[sz++] = target[i] * pp;
      }
    }
  }
  return sz;
}
const int MK = 10;
const int OVF = 1 << 30;
typedef struct LimitedSetStruct {
  int a[MK];
  int sz;
  void ins(int val) {
    if (sz >= MK) {
      sz = OVF;
      return;
    } else {
      for (int i = 0; i < sz; i++) {
        if (a[i] == val) return;
      }
      a[sz++] = val;
    }
  }
  bool ovf() { return sz == OVF; }
  void setovf() { sz = OVF; }
} LimitedSet;
int ufp[mx];
int ufs[mx];
void ufinit(int n) {
  for (int x = 0; x < n; x++) {
    ufp[x] = x;
    ufs[x] = 1;
  }
}
int uffind(int x) {
  if (ufp[x] != x) {
    ufp[x] = uffind(ufp[x]);
  }
  return ufp[x];
}
void ufunion(int x, int y) {
  if (rand() & 1) swap(x, y);
  int xr = uffind(x);
  int yr = uffind(y);
  if (xr == yr) return;
  ufp[xr] = yr;
  ufs[yr] += ufs[xr];
}
LimitedSet tmp[mx], cand[mx];
int seen[mx];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve();
  n = rint(), k = rint();
  for (int i = 0; i < n; i++) a[i] = rint();
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < x; y++) {
      int diff = abs(a[x] - a[y]);
      if (diff) {
        tmp[diff].ins((x << 16) | y);
      }
    }
  }
  for (int diff = 1; diff < mx; diff++) {
    if (tmp[diff].sz) {
      int sz = getfac(diff);
      for (int i = 0; i < sz; i++) {
        int t = target[i];
        if (tmp[diff].ovf())
          cand[t].setovf();
        else {
          for (int q = 0; q < tmp[diff].sz; q++) {
            cand[t].ins(tmp[diff].a[q]);
          }
        }
      }
    }
  }
  ufinit(mx);
  for (int id = 1; id < mx; id++) {
    if (cand[id].ovf()) continue;
    for (int q = 0; q < cand[id].sz; q++) {
      auto edge = cand[id].a[q];
      int x = edge >> 16, y = edge & 0xffff;
      ufunion(x, y);
    }
    int need = 0;
    for (int q = 0; q < cand[id].sz; q++) {
      auto edge = cand[id].a[q];
      int x = edge >> 16, y = edge & 0xffff;
      if (ufp[x] == x) {
        need += ufs[x] - 1;
        ufs[x] = 1;
      }
      if (ufp[y] == y) {
        need += ufs[y] - 1;
        ufs[y] = 1;
      }
    }
    if (need <= k) {
      printf("%d\n", id);
      return 0;
    }
    for (int q = 0; q < cand[id].sz; q++) {
      auto edge = cand[id].a[q];
      int x = edge >> 16, y = edge & 0xffff;
      ufp[x] = x;
      ufs[x] = 1;
      ufp[y] = y;
      ufs[y] = 1;
    }
  }
}

```