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