Problem Description

One day, $n$ of swimmers hold a wonderful competition in a swimming pool.

There are $n$ lanes in the swimming pool numbered from $1$ to $n$ , and the their lengths are all $m$ meters. Swimmers are also numbered from $1$ to $n$, and swimmer $i$ occpies lane $i$. The swimmers will start at position $0$, and turn back immediately when arriving at the turn line at position $m$.

They will keep swimming. The speed of swimmers may be different. The speed of the swimmer $i$ is $x_i$ meters per second.

You need to answer $q$ questions: each question gives two integers $p$ and $k$, asking for the position of swimmer $k$ after $p$ seconds.

Input

The first line contains three integers $n , m, q$ $(1 \le n \le 10^{6}, 1 \le m \le 10^{9}, 1 \le q \le 10^{6})$, indicating the number of lanes, the length of lanes and the number of questions, respectively.

The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ $(1 \le x_{i} \le 10^{9})$, indicating the speed of each swimmer.

Each of the following $q$ lines contains two integers $p_i, k_i$ $(0 \le p_i \le 10^{9}, 1 \le k_i \le n)$ representing the $i$-th question.

Output

Output $q$ lines. Each line contains a single integer, which is the answer of the $i$-th question.

1 3 2
1
5 1
7 1

1
1