#include <bits/stdc++.h>
using namespace std;
long long ara[100009], prv[100009];
vector<long long> pos[100009];
struct node {
  node *left, *right;
  long long val;
  node(long long a = 0, node *b = NULL, node *c = NULL)
      : val(a), left(b), right(c) {}
  void build(long long l, long long r) {
    if (l == r) return;
    left = new node();
    right = new node();
    long long mid = l + r >> 1;
    left->build(l, mid);
    right->build(mid + 1, r);
  }
  node *update(long long l, long long r, long long idx) {
    if (r < idx || l > idx) return this;
    if (l == r) {
      node *ret = new node(val, left, right);
      ret->val++;
      return ret;
    }
    long long mid = l + r >> 1;
    node *ret = new node(val);
    ret->left = left->update(l, mid, idx);
    ret->right = right->update(mid + 1, r, idx);
    ret->val = ret->left->val + ret->right->val;
    return ret;
  }
  long long query(long long l, long long r, long long i, long long j) {
    if (r < i || l > j) return 0;
    if (i <= l && r <= j) {
      return val;
    }
    long long mid = l + r >> 1;
    return left->query(l, mid, i, j) + right->query(mid + 1, r, i, j);
  }
} * root[100009];
int main() {
  long long n, k;
  cin >> n >> k;
  root[0] = new node();
  root[0]->build(0, 100000);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &ara[i]);
    pos[ara[i]].push_back(i);
    long long now = pos[ara[i]].size() - 1;
    if (now - k >= 0)
      ara[i] = pos[ara[i]][now - k];
    else
      ara[i] = 0;
    root[i] = root[i - 1]->update(0, 100000, ara[i]);
  }
  long long q, last = 0;
  cin >> q;
  while (q--) {
    long long x, y;
    scanf("%lld %lld", &x, &y);
    long long l = (x + last) % n + 1;
    long long r = (y + last) % n + 1;
    if (l > r) swap(l, r);
    long long sum1 = root[r]->query(0, 100000, 0, l - 1);
    long long sum2 = root[l - 1]->query(0, 100000, 0, l - 1);
    last = sum1 - sum2;
    printf("%lld\n", sum1 - sum2);
  }
  return 0;
}
