#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int n, k;
int a[N + 9];
int p[N + 9];
queue<int> q[N + 9];
vector<int> t[4 * N];
void build(int v = 1, int tl = 1, int tr = n) {
  if (tl == tr) {
    t[v] = vector<int>(1, p[tl]);
    return;
  }
  int tm = (tl + tr) >> 1;
  build(v << 1, tl, tm);
  build((v << 1) | 1, tm + 1, tr);
  merge(t[v << 1].begin(), t[v << 1].end(), t[(v << 1) | 1].begin(),
        t[(v << 1) | 1].end(), back_inserter(t[v]));
}
int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
  if (r < tl || tr < l) {
    return 0;
  }
  if (l <= tl && tr <= r) {
    return lower_bound(t[v].begin(), t[v].end(), l) - t[v].begin();
  }
  int tm = (tl + tr) >> 1;
  return get(l, r, v << 1, tl, tm) + get(l, r, (v << 1) | 1, tm + 1, tr);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    q[a[i]].push(i);
    if (((int)q[a[i]].size()) == k + 1) {
      p[i] = q[a[i]].front();
      q[a[i]].pop();
    } else {
      p[i] = -1;
    }
  }
  build();
  int m;
  scanf("%d", &m);
  int last = 0;
  while (m--) {
    int x, y;
    scanf("%d%d", &x, &y);
    int l = ((x + last) % n) + 1;
    int r = ((y + last) % n) + 1;
    if (l > r) {
      swap(l, r);
    }
    printf("%d\n", last = get(l, r));
  }
}
