20489번 - Откат 다국어

문제

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

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

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

제한

힌트