#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int S = 200;
const int B = N / S + 1;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int ans[B][B];
int sum[B][N];
int cnt[N];
int L[N], R[N], belong[N];
int a[N];
int n, k, q;
void prepare() {
  for (int i = 0; i < n; ++i) {
    belong[i] = i / S;
    L[i] = belong[i] * S;
    R[i] = min(n, L[i] + S);
  }
  set<int> st;
  for (int i = 0; i < n; ++i) sum[belong[i]][a[i]]++;
  for (int i = 0; i <= belong[n - 1]; ++i) {
    for (int j = i * S; j < R[i * S]; ++j) st.insert(a[j]);
    if (!i) continue;
    for (auto x : st) sum[i][x] += sum[i - 1][x];
  }
  for (int l = 0; l <= belong[n - 1]; ++l) {
    int res = 0;
    for (int r = l; r <= belong[n - 1]; ++r) {
      for (int i = r * S; i < R[r * S]; ++i) {
        if (cnt[a[i]] < k) {
          cnt[a[i]]++;
          res++;
        }
      }
      ans[l][r] = res;
    }
    for (int i = l * S; i < n; ++i) cnt[a[i]] = 0;
  }
}
int solve(int l, int r) {
  int ret = 0;
  int bl = belong[l], br = belong[r];
  if (bl == br || bl + 1 == br) {
    for (int i = l; i <= r; ++i) cnt[a[i]] = 0;
    for (int i = l; i <= r; ++i) {
      if (cnt[a[i]] < k) {
        cnt[a[i]]++;
        ret++;
      }
    }
    return ret;
  }
  ret = ans[bl + 1][br - 1];
  for (int i = l; i < R[l]; ++i) cnt[a[i]] = sum[br - 1][a[i]] - sum[bl][a[i]];
  for (int i = L[r]; i <= r; ++i) cnt[a[i]] = sum[br - 1][a[i]] - sum[bl][a[i]];
  for (int i = l; i < R[l]; ++i) {
    if (cnt[a[i]] < k) {
      cnt[a[i]]++;
      ret++;
    }
  }
  for (int i = L[r]; i <= r; ++i) {
    if (cnt[a[i]] < k) {
      cnt[a[i]]++;
      ret++;
    }
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  prepare();
  scanf("%d", &q);
  int ans = 0;
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    int l = (x + ans) % n;
    int r = (y + ans) % n;
    if (l > r) swap(l, r);
    printf("%d\n", ans = solve(l, r));
  }
  return 0;
}
