#include <bits/stdc++.h>
using namespace std;
int t[3000001];
int L[3000001];
int R[3000001];
int sz;
int root[300001];
int a[3000001];
int n;
vector<int> was[3000001];
void upd(int v1, int v2, int pos, int val, int tl = 0, int tr = 1000000) {
  if (tl == tr) {
    t[v2] = t[v1] + val;
    return;
  }
  int tm = (tl + tr) / 2;
  if (tm >= pos) {
    L[v2] = ++sz;
    R[v2] = R[v1];
    upd(L[v1], L[v2], pos, val, tl, tm);
  } else {
    R[v2] = ++sz;
    L[v2] = L[v1];
    upd(R[v1], R[v2], pos, val, tm + 1, tr);
  }
  t[v2] = t[L[v2]] + t[R[v2]];
}
int get(int v, int l, int r, int tl = 0, int tr = 1000000) {
  if (tr < l || tl > r || !v || l > r) return 0;
  if (tl >= l && tr <= r) return t[v];
  int tm = (tl + tr) / 2;
  return get(L[v], l, r, tl, tm) + get(R[v], l, r, tm + 1, tr);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    int len = was[x].size();
    if (len >= k) {
      a[i] = was[x][len - k];
    } else
      a[i] = 0;
    was[x].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    root[i] = ++sz;
    upd(root[i - 1], root[i], a[i], 1);
  }
  int q;
  cin >> q;
  int lastans = 0;
  while (q--) {
    int l, r;
    cin >> l >> r;
    l = (l + lastans) % n + 1;
    r = (r + lastans) % n + 1;
    bool ok = 0;
    if (l > r) {
      swap(l, r);
      ok = 1;
    }
    lastans = get(root[r], 0, l - 1) - get(root[l - 1], 0, l - 1);
    cout << lastans << "\n";
    if (ok) {
    }
  }
  return 0;
}
