Balancing Reactor Operations

You are given three integers \(n\), \(v\) and an array \(A = \{A_i\}_{i=1}^n\) of positive integers. Consider an auxiliary array \(B\) of length \(n\) which is initially identical to \(A\).

The control system performs \(n\) operations in order. In the \(i\)-th operation (\(1 \le i \le n\)), a reactor is chosen among the reactors indexed \(1,2,\ldots,i\) following these rules:

• Select the index \(j\) with the maximum current \(B_j\).
• If there is a tie, choose the one with the maximum initial \(A_j\) (after any modification as described below).
• If a tie still remains, choose the reactor with the smallest index \(j\).

After choosing \(j\), update \(B_j \leftarrow B_j + v\). We say that reactor \(j\) has been balanced one time.

There are \(m\) independent queries. In each query, you are given two integers \(x\) and \(k\). For that query, you are allowed to modify the initial value of reactor \(x\) (i.e. \(A_x\) and consequently \(B_x\)) to some non-negative integer \(s\). Your task is to find the minimum \(s\) such that if reactor \(x\) is modified to have initial value \(s\), then it is balanced at least \(k\) times during the \(n\) operations. If it is impossible to achieve \(k\) balances for reactor \(x\) (or if there is no minimum \(s\)), output 0.

Note: The queries are independent; modifications made in one query do not affect subsequent queries.

The problem involves simulating the control process as described and using techniques such as binary search to determine the minimum \(s\). All formulas are shown using \(\LaTeX\) formatting.

inputFormat

The first line contains three positive integers \(n\), \(v\) and \(m\) --- the number of reactors, the increment amount, and the number of queries, respectively.

The second line contains \(n\) positive integers \(A_1, A_2, \ldots, A_n\) representing the initial activity values of the reactors.

Then \(m\) lines follow. Each of these lines contains two integers \(x\) and \(k\) representing a query. In the query, reactor \(x\) is modified to some non-negative integer \(s\) (to be determined) so that it is balanced at least \(k\) times during the process.

It is guaranteed that \(1 \le x \le n\) for each query.

outputFormat

For each query, output a single line containing the required answer. If it is impossible to achieve at least \(k\) balances for reactor \(x\) or no minimum value exists, print 0.

sample

5 10 3
3 1 4 1 5
3 2
1 3
5 1

23
0
43