Задача №2980. Откат
Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и «откат» к предыдущей версии в случае возникновения проблем.
В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована.
На данный момент у Сергея хранятся \(n\) точек восстановления различных серверов, пронумерованных от 1 до \(n\). Точка восстановления с номером \(i\) позволяет произвести откат для сервера \(a_i\). Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \(l, l + 1, \ldots, r\) для некоторых \(l\) и \(r\).
Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \(l\), при каком минимальном \(r\) в процессе переноса будут доступны точки восстановления не менее чем \(k\) различных серверов.
Помогите Сергею.
Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 10^5\)), разделенные пробелами — количество точек восстановления и количество серверов. Вторая строка содержит \(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\) не существует.
7 3 1 2 1 3 1 2 1 4 7 3 7 1 7 1 2 2
1 4 0 6