#include <bits/stdc++.h>
using namespace std;
template <class _T>
inline void ina(_T a[], int n) {
  for (int i = 0; i < n; i++) cin >> (a[i]);
}
int TEST_CASE = 0;
template <class _T>
inline _T pow(_T a, _T b, _T m) {
  a %= m;
  _T ans = 1 % m;
  while (b) {
    if (b & 1) ans *= a, ans %= m;
    a *= a;
    a %= m;
    b >>= 1;
  }
  return ans;
}
template <class _T>
inline _T pow(_T a, _T b) {
  _T ans = 1;
  while (b) {
    if (b & 1) ans *= a;
    a *= a;
    b >>= 1;
  }
  return ans;
}
template <class _T>
inline _T add(_T a, _T b, _T m) {
  return a >= m - b ? a - (m - b) : a + b;
}
template <class _T>
inline _T multiply(_T a, _T b, _T m) {
  _T ans = 0;
  if (b > a) swap(a, b);
  while (b) {
    if (b & 1) ans = add(ans, a, m);
    b >>= 1;
    a = add(a, a, m);
  }
  return ans;
}
template <class _T>
inline _T bigpow(_T a, _T b, _T m) {
  a %= m;
  _T ans = 1 % m;
  while (b) {
    if (b & 1) ans = multiply(ans, a, m);
    a = multiply(a, a, m);
    b >>= 1;
  }
  return ans;
}
template <class _T>
inline _T modinvers(_T a, _T m) {
  return m > 2000000000LL ? bigpow(a, m - 2, m) : pow(a, m - 2, m);
}
template <class _T>
_T _egcd(_T a, _T b, _T &x, _T &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  _T _g = _egcd(b, a % b, x, y);
  _T xt = x;
  x = y, y = xt - (a / b) * y;
  return _g;
}
template <class _T>
inline _T fmodinvers(_T a, _T m) {
  _T x, y;
  _egcd(a, m, x, y);
  x %= m;
  if (x < 0) x += m;
  return x;
}
template <class _T>
inline _T _lcm(_T a, _T b) {
  return (a * b) / __gcd(a, b);
}
template <class T>
inline T SQ(T a) {
  return a * a;
}
long long SQRT(long long n) {
  long long e = sqrt(n * 1.0);
  long long l = max(0LL, e - 2), r = min(n, e + 2);
  long long ans = 0;
  while (l <= r) {
    long long m = ((l + r) >> 1);
    if (m * m <= n)
      ans = m, l = m + 1;
    else
      r = m - 1;
  }
  return ans;
}
long long CBRT(long long n) {
  long long e = cbrt(n * 1.0);
  long long l = max(0LL, e - 2), r = min(n, e + 2);
  long long ans = 0;
  while (l <= r) {
    long long m = ((l + r) >> 1);
    if (m * m * m <= n)
      ans = m, l = m + 1;
    else
      r = m - 1;
  }
  return ans;
}
const long double EPS = 1e-9;
const long double PI = acos(-1.0);
const int MX = 5e6 + 5;
long long mod = 1e9 + 7;
int sum[MX], lft[MX], rght[MX];
int avl = 1;
inline int New(int old) {
  sum[avl] = sum[old];
  lft[avl] = lft[old];
  rght[avl] = rght[old];
  return avl++;
}
int P, V;
int upd(int n, int l, int r) {
  if (P < l || P > r) return n;
  int nw = New(n);
  if (l == r) {
    sum[nw] += V;
    return nw;
  }
  int m = (l + r) >> 1;
  lft[nw] = upd(lft[nw], l, m);
  rght[nw] = upd(rght[nw], m + 1, r);
  sum[nw] = sum[lft[nw]] + sum[rght[nw]];
  return nw;
}
int qry(int n, int l, int r) {
  if (r <= P) return sum[n];
  if (l > P) return 0;
  int m = (l + r) >> 1;
  return qry(lft[n], l, m) + qry(rght[n], m + 1, r);
}
vector<int> ind[100006];
int root[100005];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, x, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    P = i;
    V = 1;
    root[i] = upd(root[i - 1], 1, n);
    ind[x].push_back(i);
    if (((int)(ind[x]).size()) > k) {
      P = ind[x][((int)(ind[x]).size()) - k - 1];
      V = -1;
      root[i] = upd(root[i], 1, n);
    }
  }
  int q, l, r;
  int ans = 0;
  cin >> q;
  while (q--) {
    cin >> l >> r;
    l += ans, r += ans;
    l %= n, r %= n;
    l++, r++;
    if (l > r) swap(l, r);
    P = r;
    ans = qry(root[r], 1, n);
    P = l - 1;
    ans -= qry(root[r], 1, n);
    cout << ans << '\n';
  }
  return 0;
}
