#include <bits/stdc++.h>
using namespace std;
int a[110000], b[110000];
int n, k;
vector<int> p[110000], t[410000];
void build(int v, int l, int r) {
  for (int i = l; i <= r; i++) t[v].push_back(b[i]);
  sort(t[v].begin(), t[v].end());
  if (l == r) return;
  int ml = (l + r) / 2;
  build(v * 2, l, ml);
  build(v * 2 + 1, ml + 1, r);
  return;
}
int get_ans(int v, int l, int r, int x, int y, int curr) {
  if (l == x && r == y) {
    vector<int>::iterator it;
    it = lower_bound(t[v].begin(), t[v].end(), curr);
    return it - t[v].begin();
  }
  int ml = (l + r) / 2;
  if (y <= ml) return get_ans(v * 2, l, ml, x, y, curr);
  if (x > ml) return get_ans(v * 2 + 1, ml + 1, r, x, y, curr);
  return get_ans(v * 2, l, ml, x, ml, curr) +
         get_ans(v * 2 + 1, ml + 1, r, ml + 1, y, curr);
}
int main() {
  ios_base::sync_with_stdio(false);
  int i, j, x, y;
  vector<int> ans;
  cin >> n >> k;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    p[a[i]].push_back(i);
  }
  for (i = 1; i <= 100000; i++) {
    for (j = p[i].size() - 1; j >= 0; j--) {
      int v = p[i][j];
      if (j - k >= 0)
        b[v] = p[i][j - k];
      else
        b[v] = -1;
    }
  }
  build(1, 1, n);
  int curr = 0, m;
  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> x >> y;
    x = ((x + curr) % n) + 1;
    y = ((y + curr) % n) + 1;
    if (x > y) swap(x, y);
    curr = get_ans(1, 1, n, x, y, x);
    ans.push_back(curr);
  }
  for (i = 0; i < m; i++) cout << ans[i] << endl;
}
