#include <bits/stdc++.h>
using namespace std;
long long used[100001], last, a[100001];
vector<long long> v[1000001], verr[100001];
void build(long long tv, long long tl, long long tr) {
  if (tl == tr)
    v[tv].push_back(used[tl]);
  else {
    long long tm = (tl + tr) / 2;
    build(tv * 2, tl, tm);
    build(tv * 2 + 1, tm + 1, tr);
    long long x = 0, y = 0;
    while (x < v[tv * 2].size() && y < v[tv * 2 + 1].size()) {
      if (v[tv * 2][x] < v[tv * 2 + 1][y]) {
        v[tv].push_back(v[tv * 2][x]);
        x++;
      } else {
        v[tv].push_back(v[tv * 2 + 1][y]);
        y++;
      }
    }
    while (x < v[tv * 2].size()) {
      v[tv].push_back(v[tv * 2][x]);
      x++;
    }
    while (y < v[tv * 2 + 1].size()) {
      v[tv].push_back(v[tv * 2 + 1][y]);
      y++;
    }
  }
}
long long ans(long long tv, long long tl, long long tr, long long l,
              long long r, long long z) {
  if (r < tl || tr < l) return 0;
  if (l <= tl && tr <= r) {
    long long x, y;
    x = 0;
    y = v[tv].size() - 1;
    while (x + 1 < y) {
      long long mm = (x + y) / 2;
      if (v[tv][mm] < z)
        x = mm;
      else
        y = mm;
    }
    if (v[tv][y] < z) return y + 1;
    if (v[tv][x] < z) return x + 1;
    return 0;
  }
  long long tm = (tl + tr) / 2;
  return ans(tv * 2, tl, tm, l, r, z) + ans(tv * 2 + 1, tm + 1, tr, l, r, z);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n, k, i, j, l, r, x, y, q;
  cin >> n >> k;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    verr[a[i]].push_back(i);
  }
  for (i = 1; i <= 100000; i++) {
    for (j = 0; j < verr[i].size(); j++) {
      if (j + 1 - k > 0) {
        used[verr[i][j]] = verr[i][j - k];
      }
    }
  }
  build(1, 1, n);
  cin >> q;
  for (i = 1; i <= q; i++) {
    cin >> x >> y;
    l = (x + last) % n + 1;
    r = (y + last) % n + 1;
    if (l > r) swap(l, r);
    last = ans(1, 1, n, l, r, l);
    cout << last << '\n';
  }
}
