Rollback

Sergey works as a system administrator at a very large company. Naturally, his duties include backing up the information stored on various servers and <> to a previous version when problems arise.

Right now Sergey is fighting a shortage of space for storing recovery information. He decided to move part of the information to new servers. Unfortunately, if something goes wrong during the move, he will not be able to roll back, so the move has to be planned carefully.

At the moment Sergey has $n$ recovery points of various servers, numbered from 1 to $n$. The recovery point with number $i$ can roll back server $a\_i$. Sergey decided to split the move into stages, and at each stage, if problems arise, the recovery points with numbers $l, l + 1, \ldots, r$ will be available.

To plan the data move optimally, Sergey needs to answer queries: for a given $l$, what is the minimum $r$ such that at least $k$ distinct servers are available during the move?

Help Sergey.

The first line of the input file contains two integers $n$ and $m$ separated by a space: the number of recovery points and the number of servers ($1 \le n, m \le 100\,000$). The second line contains $n$ integers $a\_1, a\_2, \ldots, a\_n$: the server numbers that correspond to the recovery points ($1 \le a\_i \le m$).

The third line of the input file contains $q$: the number of queries to process ($1 \le q \le 100\,000$). While processing the queries, you must maintain a number $p$, initially equal to 0. Each query is given by a pair of numbers $x\_i$ and $y\_i$; use them to obtain the query data as follows: $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$). Let the answer to the $i$-th query be $r$. After completing this query, assign $p$ the value $r$.

For each query, output one number: the minimum $r$ sought, or 0 if no such $r$ exists.