#include <bits/stdc++.h>
using namespace std;
inline int read() {
  register int x = 0, t = 1;
  register char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') t = -1, ch = getchar();
  while (ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
  return x * t;
}
int v[111111 << 5], ls[111111 << 5], rs[111111 << 5];
int tot, rt[111111];
void modify(int &x, int ff, int l, int r, int p, int w) {
  v[x = ++tot] = v[ff];
  ls[x] = ls[ff];
  rs[x] = rs[ff];
  v[x] += w;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (p <= mid)
    modify(ls[x], ls[ff], l, mid, p, w);
  else
    modify(rs[x], rs[ff], mid + 1, r, p, w);
}
int query(int r1, int r2, int l, int r, int L, int R) {
  if (L <= l && r <= R) return v[r1] - v[r2];
  int mid = (l + r) >> 1, ret = 0;
  if (L <= mid) ret += query(ls[r1], ls[r2], l, mid, L, R);
  if (R > mid) ret += query(rs[r1], rs[r2], mid + 1, r, L, R);
  return ret;
}
vector<int> S[111111];
int lst[111111], n, K, a[111111];
int main() {
  n = read();
  K = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 1; i <= n; ++i) {
    if (S[a[i]].size() >= K) lst[i] = S[a[i]][S[a[i]].size() - K];
    S[a[i]].push_back(i);
  }
  for (int i = 1; i <= n; ++i) modify(rt[i], rt[i - 1], 0, n, lst[i], 1);
  int Q = read(), ans = 0;
  while (Q--) {
    int l = (read() + ans) % n + 1, r = (read() + ans) % n + 1;
    if (l > r) swap(l, r);
    printf("%d\n", ans = query(rt[r], rt[l - 1], 0, n, 0, l - 1));
  }
  return 0;
}
