#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, a[maxn], b[maxn], root[maxn], cnt, sum[maxn], k, q;
struct node {
  int l, r, num;
} e[maxn * 40];
vector<int> p[maxn];
void update(int &x, int y, int l, int r, int pos) {
  x = ++cnt;
  e[x] = e[y];
  e[x].num++;
  if (l == r) return;
  if (pos <= ((l + r) >> 1))
    update(e[x].l, e[y].l, l, ((l + r) >> 1), pos);
  else
    update(e[x].r, e[y].r, ((l + r) >> 1) + 1, r, pos);
}
int query(int x, int y, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    return e[x].num - e[y].num;
  }
  int ans = 0;
  if (ql <= ((l + r) >> 1))
    ans += query(e[x].l, e[y].l, l, ((l + r) >> 1), ql, qr);
  if (qr > ((l + r) >> 1))
    ans += query(e[x].r, e[y].r, ((l + r) >> 1) + 1, r, ql, qr);
  return ans;
}
int main(int argc, const char *argv[]) {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    p[a[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    int pos = lower_bound(p[a[i]].begin(), p[a[i]].end(), i) - p[a[i]].begin();
    if (p[a[i]].size() <= pos + k)
      b[i] = maxn;
    else
      b[i] = p[a[i]][pos + k];
    update(root[i], root[i - 1], 1, maxn, b[i]);
  }
  scanf("%d", &q);
  int ans = 0;
  while (q--) {
    int l, r;
    scanf("%d %d", &l, &r);
    l = (l + ans) % n + 1;
    r = (r + ans) % n + 1;
    if (l > r) swap(l, r);
    ans = query(root[r], root[l - 1], 1, maxn, r + 1, maxn);
    printf("%d\n", ans);
  }
  return 0;
}
