#include <bits/stdc++.h>
using namespace std;
clock_t start;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
template <typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& q) {
  in >> q.first >> q.second;
  return in;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2>& q) {
  out << q.first << " " << q.second;
  return out;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(pair<T1, T2> p1, pair<T1, T2> p2) {
  return {p1.first + p2.first, p1.second + p2.second};
}
template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> p1, pair<T1, T2> p2) {
  return {p1.first - p2.first, p1.second - p2.second};
}
const int N = 1e5 + 1;
vector<int> seg[4 * N];
int a[N], x, n, k;
vector<int> v[N];
void merge(int v) {
  for (auto u : seg[2 * v]) seg[v].push_back(u);
  for (auto u : seg[2 * v + 1]) seg[v].push_back(u);
  sort((seg[v]).begin(), (seg[v]).end());
}
void build(int s, int e, int v) {
  if (s == e) {
    seg[v].push_back(a[s]);
    return;
  }
  int m = (s + e) / 2;
  build(s, m, 2 * v), build(m + 1, e, 2 * v + 1);
  merge(v);
}
int query(int s, int e, int v, int l, int r) {
  if (s > r || e < l || s > e) return 0;
  if (l <= s && r >= e) {
    return (int)(lower_bound((seg[v]).begin(), (seg[v]).end(), l) -
                 (seg[v]).begin());
  }
  int m = (s + e) >> 1;
  int ll = query(s, m, 2 * v, l, r);
  int rr = query(m + 1, e, 2 * v + 1, l, r);
  return ll + rr;
}
void solve() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    v[x].push_back(i);
  }
  for (int i = 1; i < N; i++) {
    for (int j = k; j < (int)((v[i]).size()); j++) {
      a[v[i][j]] = v[i][j - k];
    }
  }
  build(1, n, 1);
  int q, ans = 0;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    l = (l + ans) % n + 1;
    r = (r + ans) % n + 1;
    if (l > r) swap(l, r);
    ans = query(1, n, 1, l, r);
    cout << ans << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  start = clock();
  cout << fixed << setprecision(7);
  for (int i = 1; i <= t; i++) {
    solve();
  }
  double time_taken = double(clock() - start) / double(CLOCKS_PER_SEC);
  cerr << time_taken;
  return 0;
}
