#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
const long long mod = 1e9 + 7;
const long long nax = 500006;
const long long kmax = 106;
const long long dmax = 506;
const long long inf = 1e18;
const long long e = 1e-6;
struct vertex {
  vertex *l, *r;
  long long sum;
  vertex(vertex *l, vertex *r) : l(l), r(r), sum(0) {
    if (l) sum += l->sum;
    if (r) sum += r->sum;
  }
  vertex(long long x) : l(nullptr), r(nullptr), sum(x) {}
};
vertex *build(long long l, long long r) {
  if (l == r - 1) {
    return new vertex(0);
  }
  long long mid = (l + r) / 2;
  return new vertex(build(l, mid), build(mid, r));
}
vertex *upd(vertex *node, long long l, long long r, long long pos,
            long long val) {
  if (l == r - 1) {
    return new vertex(val);
  }
  long long mid = (l + r) / 2;
  if (pos < mid) {
    return new vertex(upd(node->l, l, mid, pos, val), node->r);
  } else {
    return new vertex(node->l, upd(node->r, mid, r, pos, val));
  }
}
long long get(vertex *node, long long l, long long r, long long lf,
              long long rg) {
  if (l >= lf && r <= rg) {
    return node->sum;
  }
  if (l >= rg || r <= lf) {
    return 0;
  }
  return get(node->l, l, (l + r) / 2, lf, rg) +
         get(node->r, (l + r) / 2, r, lf, rg);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long n, k;
  cin >> n >> k;
  vector<vertex *> roots(n + 1);
  long long B = 500006;
  roots[0] = build(0, B);
  map<long long, deque<long long>> vek;
  for (long long i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    if (vek[x].size() < k) {
      vek[x].push_back(i);
      roots[i] = upd(roots[i - 1], 0, B, i, 1);
    } else {
      roots[i] = upd(roots[i - 1], 0, B, vek[x].front(), 0);
      vek[x].pop_front();
      vek[x].push_back(i);
      roots[i] = upd(roots[i], 0, B, i, 1);
    }
  }
  long long m;
  cin >> m;
  long long ans = 0;
  while (m--) {
    long long l, r;
    cin >> l >> r;
    l = ((l + ans) % n) + 1;
    r = ((r + ans) % n) + 1;
    if (l > r) swap(l, r);
    ans = get(roots[r], 0, B, l, r + 1);
    cout << ans << '\n';
  }
  return 0;
}
