시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и <<откат>> к предыдущей версии в случае возникновения проблем.

В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована.

На данный момент у Сергея хранятся $n$ точек восстановления различных серверов, пронумерованных от 1 до $n$. Точка восстановления с номером $i$ позволяет произвести откат для сервера $a_i$. Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами $l, l + 1, \ldots, r$ для некоторых $l$ и $r$.

Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного $l$, при каком минимальном $r$ в процессе переноса будут доступны точки восстановления не менее чем $k$ различных серверов.

Помогите Сергею.

입력

Первая строка входного файла содержит два целых числа $n$ и $m$, разделенные пробелами --- количество точек восстановления и количество серверов ($1 \le n, m \le 100\,000$). Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ --- номера серверов, которым соответствуют точки восстановления ($1 \le a_i \le m$).

Третья строка входного файла содержит $q$ --- количество запросов, которые необходимо обработать ($1 \le q \le 100\,000$). В процессе обработки запросов необходимо поддерживать число~$p$, исходно оно равно~0. Каждый запрос задается парой чисел $x_i$ и $y_i$, используйте их для получения данных запроса следующим образом: $l_i = \left((x_i + p) \bmod n\right) + 1$, $k_i = \left((y_i + p) \bmod m\right) + 1$ ($1 \le l_i,x_i \le n$, $1\le k_i, y_i \le m$). Пусть ответ на $i$-й запрос равен~$r$. После выполнения этого запроса, следует присвоить $p$ значение $r$.

출력

На каждый запрос выведите одно число --- искомое минимальное $r$, либо 0, если такого $r$ не существует.

예제 입력 1

7 3
1 2 1 3 1 2 1
4
7 3
7 1
7 1
2 2

예제 출력 1

1
4
0
6