롤백

세르게이는 아주 큰 회사의 시스템 관리자로 일한다. 당연히 여러 서버에 저장된 정보를 백업하고, 문제가 생겼을 때 이전 버전으로 <<롤백>>하는 일도 그의 업무에 포함된다.

현재 세르게이는 복구용 정보를 저장할 공간이 부족한 문제와 싸우고 있다. 그는 정보의 일부를 새 서버로 옮기기로 했다. 안타깝게도 옮기는 도중에 문제가 생기면 롤백을 할 수 없으므로, 옮기는 절차를 세심하게 계획해야 한다.

현재 세르게이에게는 서로 다른 서버의 복원 지점이 $n$개 있고, 1부터 $n$까지 번호가 붙어 있다. 번호 $i$인 복원 지점은 서버 $a\_i$의 롤백을 수행할 수 있다. 세르게이는 옮기는 작업을 여러 단계로 나누기로 했고, 각 단계에서 문제가 생기면 번호 $l, l + 1, \ldots, r$인 복원 지점을 사용할 수 있다.

데이터 이전을 최적으로 계획하기 위해 세르게이는 다음 질의에 답하는 방법을 알아내야 한다. 주어진 $l$에 대해, 이전 과정에서 서로 다른 서버를 $k$개 이상 사용할 수 있게 되는 최소 $r$은 무엇인가?

세르게이를 도와주자.

입력 파일의 첫째 줄에는 공백으로 구분된 두 정수 $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$를 유지해야 하며, 처음에는 $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$이며, 그러한 $r$이 없으면 0을 출력한다.