시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и <<откат>> к предыдущей версии в случае возникновения проблем.
В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована.
На данный момент у Сергея хранятся $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$ не существует.
7 3 1 2 1 3 1 2 1 4 7 3 7 1 7 1 2 2
1 4 0 6