#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const long long linf = (long long)1e18;
const double eps = (double)1e-8;
const int mod = (int)1e9 + 7;
const int maxn = (int)1e5 + 5;
struct vertex {
  vertex* l;
  vertex* r;
  int plus;
};
void build(vertex* v, int l, int r) {
  v->plus = 0;
  v->l = nullptr;
  v->r = nullptr;
  if (l > r) return;
  if (l == r) {
    return;
  }
  v->l = new vertex;
  v->r = new vertex;
  int m = (l + r) / 2;
  build(v->l, l, m);
  build(v->r, m + 1, r);
}
int dzen(vertex* v, int l, int r, int pos, int plus) {
  if (l > r || l > pos || r < pos) return 0;
  if (l == r) {
    return v->plus + plus;
  }
  int m = (l + r) / 2;
  return dzen(v->l, l, m, pos, plus + v->plus) +
         dzen(v->r, m + 1, r, pos, plus + v->plus);
}
vertex* upd(vertex* v, int l, int r, int tl, int tr, int plus) {
  if (l > r || tl > tr) return v;
  vertex* newv = new vertex;
  newv->plus = v->plus;
  newv->l = v->l;
  newv->r = v->r;
  if (tl == l && tr == r) {
    newv->plus += plus;
    return newv;
  }
  int m = (l + r) / 2;
  newv->l = upd(v->l, l, m, tl, min(tr, m), plus);
  newv->r = upd(v->r, m + 1, r, max(m + 1, tl), tr, plus);
  return newv;
}
vertex* t[maxn];
int a[maxn];
int n, k;
vector<int> va[maxn];
int answer(int l, int r) { return dzen(t[r], 1, n, l, 0); }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = (1); i <= (int)(n); ++i) {
    cin >> a[i];
  }
  t[0] = new vertex;
  build(t[0], 1, n);
  for (int i = (1); i <= (int)(n); ++i) {
    if (va[a[i]].size() >= k)
      t[i] = upd(t[i - 1], 1, n, va[a[i]][(int)va[a[i]].size() - k] + 1, i, 1);
    else
      t[i] = upd(t[i - 1], 1, n, 1, i, 1);
    va[a[i]].push_back(i);
  }
  int last = 0;
  int T;
  cin >> T;
  for (int(numt) = (1); (numt) <= (int)(T); ++(numt)) {
    int x, y, l, r;
    cin >> x >> y;
    l = (x + last) % n + 1;
    r = (y + last) % n + 1;
    if (l > r) swap(l, r);
    last = answer(l, r);
    cout << last << "\n";
  }
  return 0;
}
