#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e9 + 7;
int n, k, ls;
int rt[N];
int a[N];
vector<int> v[N];
int tn;
struct A {
  int l, r, s;
} tr[N * 20];
int add(int k, int l, int r, int x) {
  int p = ++tn, m = l + r >> 1;
  tr[p].s = tr[k].s + 1;
  if (l == r) return p;
  if (x <= m) {
    tr[p].l = add(tr[k].l, l, m, x);
    tr[p].r = tr[k].r;
  } else {
    tr[p].l = tr[k].l;
    tr[p].r = add(tr[k].r, m + 1, r, x);
  }
  return p;
}
int find(int k, int l, int r, int L, int R) {
  if (l == L && r == R) return tr[k].s;
  int m = l + r >> 1;
  if (m >= R) return find(tr[k].l, l, m, L, R);
  if (m + 1 <= L) return find(tr[k].r, m + 1, r, L, R);
  int s = 0;
  s += find(tr[k].l, l, m, L, m);
  s += find(tr[k].r, m + 1, r, m + 1, R);
  return s;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for (int i = (1); i <= (n); i++) {
    rt[i] = rt[i - 1];
    cin >> a[i];
    v[a[i]].push_back(i);
    if (((int)v[a[i]].size()) > k)
      rt[i] = add(rt[i], 1, n, v[a[i]][((int)v[a[i]].size()) - 1 - k]);
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    l = (l + ls) % n + 1;
    r = (r + ls) % n + 1;
    if (l > r) swap(l, r);
    int ans =
        r - l + 1 - (find(rt[r], 1, n, l, r) - find(rt[l - 1], 1, n, l, r));
    ls = ans;
    cout << ls << endl;
  }
}
