E. Создание армии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как вы можете помнить из наших предыдущих контестов, Вова очень любит играть в компьютерные игры. Сейчас он играет в стратегию Rage of Empires.

В игре Вове доступны для найма n различных воинов; i-й воин имеет тип ai. Вова хочет создать сбалансированную армию, наняв какое-то подмножество воинов. Армия называется сбалансированной, если в ней присутствует не более k воинов одного типа. Конечно же, Вова хочет, чтобы его армия была как можно больше.

Но всё не так просто — Вове придётся рассмотреть q различных планов создания армии. i-й план позволяет ему нанимать только тех воинов, чей номер не меньше li и не больше ri.

Помогите Вове определить максимальный размер сбалансированной армии для каждого плана.

Обратите внимание, что параметры каждого плана заданы в изменённом виде. Подробнее в описании входных данных.

Входные данные

В первой строке записаны два числа n и k (1 ≤ n, k ≤ 100000).

Во второй строке записаны n чисел a1, a2, ... an (1 ≤ ai ≤ 100000).

В третьей строке записано единственное число q (1 ≤ q ≤ 100000).

Затем следуют q строк. i-я строка содержит два числа xi и yi, описывающие i-й план (1 ≤ xi, yi ≤ n).

Вам необходимо запоминать ответ на последний обработанный план (назовём этот ответ last). В самом начале last = 0. Числа li и ri для i-го плана восстанавливаются по следующему алгоритму:

  1. li = ((xi + last) mod n) + 1;
  2. ri = ((yi + last) mod n) + 1;
  3. Если li > ri, нужно поменять местами значения li и ri.
Выходные данные

Выведите q чисел. i-е число должно быть равно максимальному размеру сбалансированной армии при рассмотрении i-го плана.

Пример
Входные данные
6 2
1 1 1 2 2 2
5
1 6
4 3
1 1
2 6
2 6
Выходные данные
2
4
1
3
2
Примечание

В первом примере планы создания армии следующие:

  1. 1 2
  2. 1 6
  3. 6 6
  4. 2 4
  5. 4 6