\textit{Жонглирование тенисными мячиками не только укрепляет сердечно-мышечную систему и стабилизирует душевное равновесие, но и помогает динамически промоделировать персистентную структуру данных...} \textit{(Сергей Копелиович - из непроизнесённого во время лекции)} \includegraphics{https://static.e-olymp.com/content/cf/cf849a030592ae756f0a36bbde1abaf9b6d6e94c.jpg} Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и "откат" к предыдущей версии в случае возникновения проблем. В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована. На данный момент у Сергея хранятся \textbf{n} точек восстановления различных серверов, пронумерованных от \textbf{1} до \textbf{n}. Точка восстановления с номером \textbf{i} позволяет произвести откат для сервера \textbf{a_i}. Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \textbf{l}, \textbf{l + 1}, ..., \textbf{r} для некоторых \textbf{l} и \textbf{r}. Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \textbf{l}, при каком минимальном \textbf{r} в процессе переноса будут доступны точки восстановления не менее чем \textbf{k} различных серверов. Помогите Сергею. \InputFile Первая строка входного файла содержит два целых числа \textbf{n} и \textbf{m}, разделенные пробелами - количество точек восстановления и количество серверов (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{100000}). Вторая строка содержит \textbf{n} целых чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n} - номера серверов, которым соответствуют точки восстановления (\textbf{1} ≤ \textbf{a_i} ≤ \textbf{m}). Третья строка входного файла содержит \textbf{q} - количество запросов, которые необходимо обработать (\textbf{1} ≤ \textbf{q} ≤ \textbf{100000}). В процессе обработки запросов необходимо поддерживать число \textbf{p}, исходно оно равно \textbf{0}. Каждый запрос задается парой чисел \textbf{x_i} и \textbf{y_i}, используйте их для получения данных запроса следующим образом: \textbf{l_i} = ((\textbf{x_i} + \textbf{p}) \textbf{mod n}) + \textbf{1}, \textbf{k_i} = ((\textbf{y_i} + \textbf{p}) \textbf{mod m}) + \textbf{1} (\textbf{1} ≤ \textbf{l_i}, \textbf{x_i} ≤ \textbf{n}, \textbf{1} ≤ \textbf{k_i}, \textbf{y_i} ≤ \textbf{m}). Пусть ответ на \textbf{i}-й запрос равен \textbf{r}. После выполнения этого запроса следует присвоить \textbf{p} значение \textbf{r}. \OutputFile На каждый запрос выведите одно число - искомое минимальное \textbf{r}, либо \textbf{0}, если такого \textbf{r} не существует.