#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int const N = 100 * 1000 + 16;
int const M = 1000 * 1000 * 1000 + 7;
int n, k;
int a[N];
int b[N];
int c[N];
vector<int> idx[N];
struct seg {
  int x;
  int lf, rg;
  seg* l = 0;
  seg* r = 0;
  seg(seg* t) { *this = *t; }
  seg(int L, int R) {
    lf = L;
    rg = R;
    x = 0;
    if (L == R) return;
    int M = L + R >> 1;
    l = new seg(L, M);
    r = new seg(M + 1, R);
  }
  int query(int L, int R) {
    if (L <= lf && rg <= R) return x;
    int M = lf + rg >> 1;
    int sum = 0;
    if (L <= M) sum += l->query(L, R);
    if (M < R) sum += r->query(L, R);
    return sum;
  }
  seg* upd(int idx, int v) {
    seg* tmp = new seg(this);
    if (lf == rg) {
      tmp->x = v;
    } else {
      int M = lf + rg >> 1;
      if (idx <= M)
        tmp->l = tmp->l->upd(idx, v);
      else
        tmp->r = tmp->r->upd(idx, v);
      tmp->x = tmp->l->x + tmp->r->x;
    }
    return tmp;
  }
};
seg* t[N];
int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);
  cin >> n >> k;
  t[0] = new seg(1, n);
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    idx[x].emplace_back(i);
    t[i] = t[i - 1]->upd(i, 1);
    if (++b[x] > k) t[i] = t[i]->upd(idx[x][b[x] - k - 1], 0);
  }
  int q;
  cin >> q;
  int last = 0;
  while (q--) {
    int xi, yi;
    cin >> xi >> yi;
    int l = (xi + last) % n + 1;
    int r = (yi + last) % n + 1;
    if (l > r) swap(l, r);
    last = t[r]->query(l, r);
    cout << last << "\n";
  }
  cout << flush;
}
