#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
vector<int> f[N];
int ls[N * 40], rs[N * 40], num[N * 40], cnt, rt[N];
int n, m, a[N];
void modify(int &now, int l, int r, int k) {
  ++cnt;
  ls[cnt] = ls[now], rs[cnt] = rs[now], num[cnt] = num[now] + 1;
  now = cnt;
  if (l + 1 == r) return;
  int mid = (l + r) >> 1;
  if (k < mid) modify(ls[now], l, mid, k);
  if (k >= mid) modify(rs[now], mid, r, k);
}
int Query(int rt1, int rt2, int l, int r, int k) {
  if (r - 1 <= k) return num[rt2] - num[rt1];
  int mid = (l + r) >> 1;
  int ans = 0;
  ans += Query(ls[rt1], ls[rt2], l, mid, k);
  if (k >= mid) ans += Query(rs[rt1], rs[rt2], mid, r, k);
  return ans;
}
int main() {
  int x, y, z;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &x);
    f[x].push_back(i);
    y = 0;
    z = f[x].size();
    if (z > m) y = f[x][z - m - 1];
    rt[i] = rt[i - 1];
    modify(rt[i], 0, n + 1, y);
  }
  scanf("%d", &m);
  int ans = 0;
  int l, r;
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &x, &y);
    l = (x + ans) % n + 1;
    r = (y + ans) % n + 1;
    if (l > r) swap(l, r);
    ans = Query(rt[l - 1], rt[r], 0, n + 1, l - 1);
    printf("%d\n", ans);
  }
  return 0;
}
