Rollback
Juggling tennis balls not only enhances cardiovascular health and balances the spirit, but also aids in dynamically modeling a persistent data structure...
(Serhiy Kopeliovych - from an unspoken lecture)
Serhiy is a system administrator at a large company. His responsibilities include backing up data stored on various servers and reverting to previous versions if issues arise.
Currently, Serhiy faces a challenge with insufficient storage space for recovery information. He plans to move some of this data to new servers. However, if an error occurs during the transfer, he won't be able to revert, so the transfer must be meticulously planned.
Serhiy has n recovery points for different servers, numbered from 1 to n. The recovery point numbered i allows a rollback for server a_i. He decided to divide the transfer into stages, where, in case of issues, recovery points numbered l, l + 1, ..., r will be accessible for some l and r.
To optimize the data transfer, Serhiy needs to answer queries: for a given l, what is the minimum r such that during the transfer, recovery points for at least k different servers will be available?
Help Serhiy with this task.
Input
The first line of the input contains two integers n and m, separated by a space - the number of recovery points and the number of servers (1 ≤ n, m ≤ 100000). The second line contains n integers a_1, a_2, ..., a_n - the server numbers corresponding to the recovery points (1 ≤ a_i ≤ m).
The third line of the input contains q - the number of queries to process (1 ≤ q ≤ 100000). During query processing, maintain a number p, initially set to 0. Each query is given by a pair of numbers x_i and y_i, which are used to calculate the query data as follows:
l_i = ((x_i + p) mod n) + 1, k_i = ((y_i + p) mod m) + 1 (1 ≤ l_i, x_i ≤ n, 1 ≤ k_i, y_i ≤ m).
Let the answer to the i-th query be r. After executing this query, update p to the value r.
Output
For each query, output a single number - the required minimum r, or 0 if such r does not exist.