Откат

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

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

На данный момент у Сергея хранятся $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$ не существует.