#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
struct Tree {
  int val;
  Tree *l, *r;
  Tree() {
    val = 0;
    l = r = 0;
  }
} tree[100005];
vector<int> g[100005];
int num[100005], pos[100005];
void build(Tree *&t, int l, int r) {
  if (!t) t = new Tree;
  if (l == r) {
    t->val = (l == pos[1]);
    return;
  }
  int mid = (l + r) >> 1;
  build(t->l, l, mid);
  build(t->r, mid + 1, r);
  t->val = t->l->val + t->r->val;
}
void modify(Tree *pre, Tree *cur, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) {
    cur->val = pre->val + 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid && qr >= l) {
    cur->r = pre->r;
    cur->l = new Tree;
    modify(pre->l, cur->l, l, mid, ql, qr);
  }
  if (ql <= r && qr >= mid + 1) {
    cur->l = pre->l;
    cur->r = new Tree;
    modify(pre->r, cur->r, mid + 1, r, ql, qr);
  }
  cur->val = cur->l->val + cur->r->val;
}
int query(Tree *root, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) return root->val;
  int mid = (l + r) >> 1, ans = 0;
  if (ql <= mid && qr >= l) ans += query(root->l, l, mid, ql, qr);
  if (ql <= r && qr >= mid + 1) ans += query(root->r, mid + 1, r, ql, qr);
  return ans;
}
int main() {
  int i, n, k, q, l, r, last = 0;
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i++) scanf("%d", &num[i]);
  for (i = n; i >= 1; i--) {
    if (g[num[i]].size() < k)
      pos[i] = n + 1;
    else
      pos[i] = g[num[i]][g[num[i]].size() - k];
    g[num[i]].emplace_back(i);
  }
  Tree *temp = &tree[1];
  build(temp, 1, n + 1);
  for (i = 2; i <= n; i++)
    modify(&tree[i - 1], &tree[i], 1, n + 1, pos[i], pos[i]);
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &l, &r);
    l = (l + last) % n + 1;
    r = (r + last) % n + 1;
    if (l > r) swap(l, r);
    last = query(&tree[r], 1, n + 1, r + 1, n + 1) -
           (l > 1 ? query(&tree[l - 1], 1, n + 1, r + 1, n + 1) : 0);
    printf("%d\n", last);
  }
}
