\textit{Жонглюванння тенісними м'ячиками не лише укріплює сердцево-м'язову систему і стабілізує духовну рівновагу, але й допомагає динамічно промоделювати персистентну структуру даних...} \textit{(Сергій Копеліович - з невисказаного під час лекції)} \includegraphics{https://static.e-olymp.com/content/cf/cf849a030592ae756f0a36bbde1abaf9b6d6e94c.jpg} Сергій працює системним адміністратором у дуже крупній компанії. Природньо, у круг його обов'язків входить резервне копіювання інформації, що зберігається на різних серверах і "відкат" до попередньої версії у випадку виникнення проблем. У даний момент Сергій бореться з проблемою недостачі місця для зберігання інформації для відновлення. Він вирішив перенести частину інформації на нові сервери. На жаль, якщо щось станеться під час переносу, він не зможе здійснити відткат, тому процедура перенесення повинна бути ретельно спланована. На даний момент у Сергія зберігається \textbf{n} точок відновлення різних серверів, пронумерованих від \textbf{1} до \textbf{n}. Точка відновлення з номером \textbf{i} дозволяє провести відкат для серверу \textbf{a_i}. Сергій вирішив розбити перенесення на етапи, при цьому на кожному етапі у випадку виникнення проблем будуть доступні точки відновлення з номерами \textbf{l}, \textbf{l + 1}, ..., \textbf{r} для деяких \textbf{l} і \textbf{r}. Для того, щоб спланувати перенесення даних оптимальним чином, Сергію необхідно навчитись відповідати на запити: для заданого \textbf{l}, при якому мінімальному \textbf{r} у процесі переносення будуть доступні точки відновлення не менше ніж \textbf{k} різних серверів. Допоможіть Сергію. \InputFile Перший рядок вхідного файлу містить два цілих числа \textbf{n} і \textbf{m}, відокремлених пропусками - кількість точок відновлення і кількість серверів (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{100000}). Другий рядок містит \textbf{n} цілих чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n} - номери серверів, яким відповідають точки відновлення (\textbf{1} ≤ \textbf{a_i} ≤ \textbf{m}). Третій рядок вхідного файлу містить \textbf{q} - кількість запитів, які необхідно опрацювати (\textbf{1} ≤ \textbf{q} ≤ \textbf{100000}). У процесі опрацювання запитів необхідно підтримувати число \textbf{p}, на початку воно рівне \textbf{0}. Кожен запитс задається парою чисел \textbf{x_i} та \textbf{y_i}, використовуйте їх для отримання даних запиту наступним чином: \textbf{l_i} = ((\textbf{x_i} + \textbf{p}) \textbf{mod n}) + \textbf{1}, \textbf{k_i} = ((\textbf{y_i} + \textbf{p}) \textbf{mod m}) + \textbf{1} (\textbf{1} ≤ \textbf{l_i}, \textbf{x_i} ≤ \textbf{n}, \textbf{1} ≤ \textbf{k_i}, \textbf{y_i} ≤ \textbf{m}). Нехай відповідь на \textbf{i}-й запит дорівнює \textbf{r}. Після виконання цього запиту слід присвоїти \textbf{p} значення \textbf{r}. \OutputFile На кожен запит виведіть одне число - шукане мініимальне \textbf{r}, або \textbf{0}, якщо такого \textbf{r} не існує.