Відкат#1973

Відкат

4 секунди

256 мегабайтів

Дуже легка

Жонглювання тенісними м'ячами не лише укріплює серцево-судинну та м'язову системи й стабілізує дух, а й допомагає динамічно моделювати стійкі структури даних...

(Сергій Копелевич — з нездійсненої лекції)

Сергій — системний адміністратор у великій компанії. До його обов'язків входить створення резервних копій інформації, що зберігається на різних серверах, а також відновлення до попередніх версій у разі виникнення проблем.

Наразі Сергій зіштовхнувся з нестачею місця для резервних копій. Він вирішив перенести частину цих даних на нові сервери. На жаль, якщо щось піде не так під час перенесення, він не зможе виконати відкат, тому процедуру перенесення слід ретельно спланувати.

Зараз у Сергія є $n$ точок відновлення для різних серверів, пронумерованих від $1$ до $n$ . Точка відновлення з номером $i$ дозволяє відкотитися для сервера $a_{i}$ a_i. Сергій вирішив розбити перенесення на етапи так, щоб на кожному етапі, у разі проблем, були доступні точки відновлення з номерами $l$ , $l + 1$ l + 1, $\dots$ , $r$ для деяких $l$ та $r$ .

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

Допоможіть Сергію.

Вхідні дані

У першому рядку вхідних даних містяться два цілі числа $n$ і $m$ , розділені пробілом — кількість точок відновлення та кількість серверів ( $1 \leq n, m \leq 100000$ 1 \leq n,\ m \leq 100\,000). У другому рядку записано $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n — номери серверів, до яких належать відповідні точки відновлення ( $1 \leq a_{i} \leq m$ 1 \leq a_i \leq m).

У третьому рядку задано число $q$ — кількість запитів ( $1 \leq q \leq 100000$ 1 \leq q \leq 100\,000). Під час обробки запитів варто підтримувати число $p$ , яке спочатку дорівнює $0$ . Кожен запит задається парою чисел $x_{i}$ x_i та $y_{i}$ y_i. Використовуйте їх для обчислення даних запиту так:

l_{i} = ((x_{i} + p) mod n) + 1, k_{i} = ((y_{i} + p) mod m) + 1 (1 \leq l_{i}, x_{i} \leq n, 1 \leq k_{i}, y_{i} \leq m)

l_i = ((x_i + p) \bmod n) + 1, \quad k_i = ((y_i + p) \bmod m) + 1 \quad (1 \leq l_i,\ x_i \leq n, \ 1 \leq k_i,\ y_i \leq m)

Нехай відповідь на $i$ -й запит — $r$ . Після обробки цього запиту значення $p$ змінюється на $r$ .

Вихідні дані

Для кожного запиту виведіть одне число — шуканий мінімальний $r$ , або 0, якщо такого $r$ не існує.

Приклади

Приклад 1