Задача I. Откат ≡

Условие

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

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

На данный момент у Сергея хранятся n точек восстановления различных серверов, пронумерованных от 1 до n. Точка восстановления с номером i позволяет произвести откат для сервера a_i. Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами l, l + 1, …, r для некоторых l и r.

Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного l, при каком минимальном r в процессе переноса будут доступны точки восстановления не менее чем k различных серверов.

Помогите Сергею.

Формат входного файла

Первая строка входного файла содержит два целых числа n и m, разделенные пробелами — количество точек восстановления и количество серверов (1 ≤ n, m ≤ 100 000). Вторая строка содержит n целых чисел a₁, a₂, …, a_n — номера серверов, которым соответствуют точки восстановления (1 ≤ a_i ≤ m).

Третья строка входного файла содержит q — количество запросов, которые необходимо обработать (1 ≤ q ≤ 100 000). В процессе обработки запросов необходимо поддерживать число 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 не существует.

Примеры тестов

7 3
1 2 1 3 1 2 1
4
7 3
7 1
7 1
2 2

1
4
0
6