#include <bits/stdc++.h>
using namespace std;
int arr[100100];
typedef struct Node* pNode;
struct Node {
  int data;
  pNode left, right;
  Node() {
    this->data = 0;
    this->left = this->right = NULL;
  }
  Node(int _data) {
    this->data = _data;
    this->left = this->right = NULL;
  }
  Node(pNode _left, pNode _right) {
    this->data = 0;
    this->left = _left;
    this->right = _right;
  }
};
int tamST;
struct SegmentTree {
  pNode root;
  SegmentTree(){};
  void build1(int tam) {
    tamST = tam;
    this->root = build();
  }
  pNode build(int low = 0, int high = tamST - 1) {
    if (low == high) {
      return new Node;
    }
    int mid = (low + high) >> 1;
    return new Node(build(low, mid), build(mid + 1, high));
  }
  pNode update(pNode n, int& pos, int val, int low = 0, int high = tamST - 1) {
    if (low == high && pos == low) return new Node(val);
    int mid = (low + high) >> 1;
    pNode left = n->left;
    pNode right = n->right;
    if (pos <= mid)
      left = update(n->left, pos, val, low, mid);
    else
      right = update(n->right, pos, val, mid + 1, high);
    pNode now = new Node(left, right);
    now->data = left->data + right->data;
    return now;
  }
  int query(pNode n, int& qlow, int& qhigh, int low = 0, int high = tamST - 1) {
    if (qlow > high || qhigh < low) return 0;
    if (qlow <= low && qhigh >= high) return n->data;
    int mid = (low + high) >> 1;
    return query(n->left, qlow, qhigh, low, mid) +
           query(n->right, qlow, qhigh, mid + 1, high);
  }
  int query(int& qlow, int& qhigh) { return query(this->root, qlow, qhigh); }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> arr[i];
  int q;
  cin >> q;
  int x, y;
  int last = 0;
  int l, r;
  std::vector<queue<int> > v(100100, queue<int>());
  int pos = 0;
  std::vector<SegmentTree> segments(n + 10);
  segments[pos++].build1(100100);
  for (int i = n - 1; i >= 0; --i) {
    if (v[arr[i]].size() < k) {
      v[arr[i]].push(i);
      segments[pos].root =
          segments[pos - 1].update(segments[pos - 1].root, i, 1);
    } else if (v[arr[i]].size() == k) {
      segments[pos].root = segments[pos - 1].update(segments[pos - 1].root,
                                                    v[arr[i]].front(), 0);
      v[arr[i]].pop();
      v[arr[i]].push(i);
      segments[pos].root = segments[pos].update(segments[pos].root, i, 1);
    }
    ++pos;
  }
  while (q--) {
    cin >> x >> y;
    l = ((x + last) % n) + 1;
    r = ((y + last) % n) + 1;
    if (l > r) swap(l, r);
    l--;
    r--;
    last = segments[n - l].query(l, r);
    cout << last << "\n";
  }
  return 0;
}
