#include <bits/stdc++.h>
const long long inf = 0x3f3f3f3f3f3f3f3LL;
const long long mod = 1e9 + 7;
using namespace std;
template <class T>
void smin(T& a, T val) {
  if (a > val) a = val;
}
template <class T>
void smax(T& a, T val) {
  if (a < val) a = val;
}
template <typename T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  bool first = true;
  os << "[";
  for (auto i : v) {
    if (!first) os << ", ";
    os << i;
    first = false;
  }
  return os << "]";
}
const long long N = 1e5 + 10;
long long q, x, y, n, k, a[N], cokddeikm[N];
std::vector<long long> v[N];
std::vector<long long> seg[4 * N];
void build(long long node, long long l, long long r) {
  if (l == r) {
    seg[node].push_back(cokddeikm[l]);
    return;
  }
  long long mid = (l + r) >> 1;
  build(2 * node, l, mid);
  build(2 * node + 1, mid + 1, r);
  long long left = 2 * node, right = 2 * node + 1;
  merge(seg[left].begin(), seg[left].end(), seg[right].begin(),
        seg[right].end(), back_inserter(seg[node]));
}
long long query(long long node, long long l, long long r, long long ql,
                long long qr) {
  if (l > r or l > qr or r < ql) {
    return 0;
  }
  if (ql <= l and r <= qr) {
    return lower_bound(seg[node].begin(), seg[node].end(), ql) -
           seg[node].begin();
  }
  long long mid = (l + r) >> 1;
  return query(2 * node, l, mid, ql, qr) +
         query(2 * node + 1, mid + 1, r, ql, qr);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> k;
  for (long long i = 1; i <= n; ++i) {
    cin >> a[i];
    v[a[i]].push_back(i);
  }
  for (long long i = 1; i <= N - 10; ++i) {
    if (v[i].empty()) continue;
    for (long long j = 0; j < (long long)(v[i].size()); ++j) {
      if (j - k >= 0) cokddeikm[v[i][j]] = v[i][j - k];
    }
  }
  build(1, 1, n);
  cin >> q;
  long long last = 0;
  while (q--) {
    cin >> x >> y;
    long long tt = (x + last) % n + 1;
    long long tt2 = (y + last) % n + 1;
    if (tt > tt2) swap(tt, tt2);
    last = query(1, 1, n, tt, tt2);
    cout << last << '\n';
  }
  return 0;
}
