#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int inf = numeric_limits<int>::max() / 2;
const long double eps = 1e-9;
const long double pi = acos(-1);
template <typename T>
inline bool mineq(T& a, T b) {
  return (a > b) ? (a = b, 1) : 0;
}
template <typename T>
inline bool maxeq(T& a, T b) {
  return (a < b) ? (a = b, 1) : 0;
}
inline void solve(), read();
const string file = "";
int main() {
  if (file != "") {
    freopen((file + ".in").c_str(), "r", stdin);
    freopen((file + ".out").c_str(), "w", stdout);
  }
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  read();
  solve();
  return 0;
}
struct segment {
  int n;
  vector<vector<int> > t;
  segment() {}
  segment(vector<int>& a) {
    int l = log2((int)((a).size())) + 1;
    n = 1ll << l;
    t.resize(2 * n);
    build(a);
  }
  void build(vector<int>& a) {
    for (int i = 0; i < (int)((a).size()); i++) {
      t[i + n] = {a[i]};
    }
    for (int i = n - 1; i >= 0; i--) {
      t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
  }
  vector<int> merge(vector<int>& a, vector<int>& b) {
    vector<int> c;
    ::merge((a).begin(), (a).end(), (b).begin(), (b).end(), back_inserter(c));
    return c;
  }
  int get(int v, int tl, int tr, int l, int r, int p) {
    if (tl > r || tr < l) {
      return 0;
    }
    if (l <= tl && tr <= r) {
      int cur = lower_bound((t[v]).begin(), (t[v]).end(), p) - t[v].begin();
      return cur;
    }
    int tm = (tl + tr) / 2;
    int v1 = get(2 * v, tl, tm, l, r, p);
    int v2 = get(2 * v + 1, tm + 1, tr, l, r, p);
    return v1 + v2;
  }
};
const int MAXN = 1e5 + 10;
int n, k, q;
vector<int> a, b;
vector<int> prv[MAXN];
segment st;
inline void solve() {
  b.assign(n, -1);
  for (int i = 0; i < n; i++) {
    if ((int)((prv[a[i]]).size()) >= k) {
      b[i] = prv[a[i]][(int)((prv[a[i]]).size()) - k];
    }
    prv[a[i]].push_back(i);
  }
  st = segment(b);
  int last = 0;
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    int l = (x + last) % n;
    int r = (y + last) % n;
    if (l > r) {
      swap(l, r);
    }
    last = st.get(1, 0, st.n - 1, l, r, l);
    cout << last << "\n";
  }
}
inline void read() {
  cin >> n >> k;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  cin >> q;
}
