#include <bits/stdc++.h>
using namespace std;
vector<int> pos[100005];
int n, k, m, rt[100005], val[100005 << 5], lc[100005 << 5], rc[100005 << 5],
    cnt;
void insert(int &x, int l, int r, int num) {
  lc[++cnt] = lc[x];
  rc[cnt] = rc[x];
  val[cnt] = val[x] + 1;
  x = cnt;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (num <= mid)
    insert(lc[x], l, mid, num);
  else
    insert(rc[x], mid + 1, r, num);
}
int ask(int x, int y, int l, int r, int num) {
  if (r <= num) return val[y] - val[x];
  int mid = (l + r) >> 1, ans = 0;
  ans = ask(lc[x], lc[y], l, mid, num);
  if (num > mid) ans += ask(rc[x], rc[y], mid + 1, r, num);
  return ans;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1, x; i <= n; i++) {
    scanf("%d", &x);
    pos[x].push_back(i);
    int sz = pos[x].size();
    if (sz > k)
      sz = pos[x][sz - k - 1];
    else
      sz = 0;
    rt[i] = rt[i - 1];
    insert(rt[i], 0, n, sz);
  }
  scanf("%d", &m);
  int ans = 0;
  while (m--) {
    int l, r;
    scanf("%d%d", &l, &r);
    l = (l + ans) % n + 1;
    r = (r + ans) % n + 1;
    if (l > r) swap(l, r);
    printf("%d\n", ans = ask(rt[l - 1], rt[r], 0, n, l - 1));
  }
}
