#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 100000;
vector<int> seg[4 * N], p[N], a(N);
void build(int idx = 1, int L = 0, int R = n - 1) {
  if (L == R) {
    seg[idx].push_back(a[L]);
    return;
  }
  build(2 * idx, L, (L + R) / 2);
  build(2 * idx + 1, (L + R) / 2 + 1, R);
  merge(seg[2 * idx].begin(), seg[2 * idx].end(), seg[2 * idx + 1].begin(),
        seg[2 * idx + 1].end(), back_inserter(seg[idx]));
}
int query(int st, int en, int l, int idx = 1, int L = 0, int R = n - 1) {
  if (L > en || R < st) {
    return 0;
  }
  if (L >= st && R <= en) {
    return lower_bound(seg[idx].begin(), seg[idx].end(), l) - seg[idx].begin();
  }
  return query(st, en, l, 2 * idx, L, (L + R) / 2) +
         query(st, en, l, 2 * idx + 1, (L + R) / 2 + 1, R);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x, --x;
    p[x].push_back(i);
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < p[i].size(); ++j) {
      a[p[i][j]] = j < k ? -1 : p[i][j - k];
    }
  }
  build();
  int last = 0, q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    l = (l + last) % n;
    r = (r + last) % n;
    cout << (last = query(min(l, r), max(l, r), min(l, r))) << "\n";
  }
  return 0;
}
