#include <bits/stdc++.h>
using namespace std;
int n, k, q;
vector<int> style;
vector<vector<int> > place;
vector<int> base;
vector<vector<int> > t;
void read() {
  cin >> n >> k;
  style.resize(n + 1);
  place.resize(100001);
  base.resize(n + 1);
  t.resize(n * 4 + 4);
  for (int i = 1; i < n + 1; i++) cin >> style[i];
  cin >> q;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = vector<int>(1, base[tl]);
  } else {
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(),
          t[v * 2 + 1].end(), back_inserter(t[v]));
  }
}
int query(int v, int tl, int tr, int l, int r, int x) {
  if (l > r) return 0;
  if (tl == l && tr == r) {
    vector<int>::iterator pos = lower_bound(t[v].begin(), t[v].end(), x);
    return pos - t[v].begin();
  } else {
    int tm = (tl + tr) / 2;
    return (query(v * 2, tl, tm, l, min(tm, r), x) +
            query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x));
  }
}
int main() {
  int x, y, last = 0;
  int l, r;
  read();
  for (int i = 1; i < n + 1; i++) place[style[i]].push_back(i);
  for (int i = 1; i < 100001; i++) {
    for (int j = 0; j < place[i].size(); j++) {
      if (j >= k)
        base[place[i][j]] = place[i][j - k];
      else
        base[place[i][j]] = -1;
    }
  }
  place.clear();
  style.clear();
  build(1, 1, n);
  while (q--) {
    cin >> x >> y;
    l = ((x + last) % n) + 1;
    r = ((y + last) % n) + 1;
    if (l > r) swap(l, r);
    last = query(1, 1, n, l, r, l);
    cout << last << endl;
  }
  return 0;
}
