#include <bits/stdc++.h>
using namespace std;
pair<int, int> par[5000];
int tab[5000];
int rozn[1000002][12];
int r[1000002];
int t;
int find(int x) {
  if (par[x].second != t || par[x].first == x) return x;
  par[x].first = find(par[x].first);
  return par[x].first;
}
void link(int a, int b) {
  if (find(a) == find(b)) return;
  par[find(a)].first = find(b);
  par[find(a)].second = t;
}
int main() {
  int n, k, naj;
  scanf("%d%d", &n, &k);
  int g = (k + 1) * k / 2;
  for (int i = 0; i < n; i++) {
    scanf("%d", &tab[i]);
  }
  sort(tab, tab + n);
  for (int i = 0; i <= tab[n - 1]; i++) {
    r[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (r[tab[j] - tab[i]] > g) continue;
      rozn[tab[j] - tab[i]][r[tab[j] - tab[i]]] = (i << 13) + j;
      r[tab[j] - tab[i]] += 1;
    }
  }
  for (int i = 0; i < n; i++) par[i] = make_pair(i, 0);
  int err, st, nd, siz;
  for (int w = max(1, n - 5); w <= tab[n - 1] + 1; w++) {
    t = w;
    err = 0;
    int u = k + 1;
    bool ok = 1;
    for (int i = w; (i <= tab[n - 1]); i += w) {
      err += r[i];
      if (err > g) {
        ok = 0;
        break;
      }
      for (int j = 0; j < r[i]; j++) {
        st = (rozn[i][j] >> 13);
        nd = rozn[i][j] - (st << 13);
        u -= (find(st) != find(nd));
        if (!u) {
          ok = 0;
          break;
        }
        link(st, nd);
      }
      if (!ok) break;
    }
    if (ok) {
      printf("%d\n", w);
      return 0;
    }
  }
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
pair<int, int> par[5000];
int tab[5000];
int rozn[1000002][12];
int r[1000002];
int t;
int find(int x) {
  if (par[x].second != t || par[x].first == x) return x;
  par[x].first = find(par[x].first);
  return par[x].first;
}
void link(int a, int b) {
  if (find(a) == find(b)) return;
  par[find(a)].first = find(b);
  par[find(a)].second = t;
}
int main() {
  int n, k, naj;
  scanf("%d%d", &n, &k);
  int g = (k + 1) * k / 2;
  for (int i = 0; i < n; i++) {
    scanf("%d", &tab[i]);
  }
  sort(tab, tab + n);
  for (int i = 0; i <= tab[n - 1]; i++) {
    r[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (r[tab[j] - tab[i]] > g) continue;
      rozn[tab[j] - tab[i]][r[tab[j] - tab[i]]] = (i << 13) + j;
      r[tab[j] - tab[i]] += 1;
    }
  }
  for (int i = 0; i < n; i++) par[i] = make_pair(i, 0);
  int err, st, nd, siz;
  for (int w = max(1, n - 5); w <= tab[n - 1] + 1; w++) {
    t = w;
    err = 0;
    int u = k + 1;
    bool ok = 1;
    for (int i = w; (i <= tab[n - 1]); i += w) {
      err += r[i];
      if (err > g) {
        ok = 0;
        break;
      }
      for (int j = 0; j < r[i]; j++) {
        st = (rozn[i][j] >> 13);
        nd = rozn[i][j] - (st << 13);
        u -= (find(st) != find(nd));
        if (!u) {
          ok = 0;
          break;
        }
        link(st, nd);
      }
      if (!ok) break;
    }
    if (ok) {
      printf("%d\n", w);
      return 0;
    }
  }
}

```