#include <bits/stdc++.h>
using namespace std;
int read() {
  char ch = getchar();
  int h = 0, t = 1;
  while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
  if (ch == '-') t = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') {
    h = h * 10 + ch - '0';
    ch = getchar();
  }
  return h * t;
}
const int MAXN = 100100;
int N, K, Q, node, a[MAXN], head[MAXN], fa[MAXN][21], Root[MAXN];
struct Seg {
  int lc, rc, sum;
} t[MAXN * 20];
void Add(int &now, int l, int r, int pos) {
  t[++node] = t[now];
  t[now = node].sum++;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    Add(t[now].lc, l, mid, pos);
  else
    Add(t[now].rc, mid + 1, r, pos);
}
int Query(int L, int R, int l, int r, int gl, int gr) {
  if (l >= gl && r <= gr) return t[R].sum - t[L].sum;
  int mid = (l + r) >> 1, ans = 0;
  if (gl <= mid) ans += Query(t[L].lc, t[R].lc, l, mid, gl, gr);
  if (gr >= mid + 1) ans += Query(t[L].rc, t[R].rc, mid + 1, r, gl, gr);
  return ans;
}
int main() {
  N = read();
  K = read();
  for (int i = 1; i <= N; i++) {
    a[i] = read();
    fa[i][0] = head[a[i]];
    head[a[i]] = i;
  }
  for (int i = 1; i <= N; i++) {
    for (int k = 1; k <= 20; k++) fa[i][k] = fa[fa[i][k - 1]][k - 1];
    int pos = i;
    for (int k = 20; k >= 0; k--)
      if (K & (1 << k)) pos = fa[pos][k];
    Root[i] = Root[i - 1];
    if (pos) Add(Root[i], 1, N, pos);
  }
  Q = read();
  for (int i = 1, lst = 0; i <= Q; i++) {
    int x = read(), y = read();
    int l = (x + lst) % N + 1, r = (y + lst) % N + 1;
    if (l > r) swap(l, r);
    printf("%d\n", lst = (r - l + 1) - Query(Root[l - 1], Root[r], 1, N, l, r));
  }
  return 0;
}
