Dinosaur's Dietary Journey

There are \(10^6\) trees numbered from \(1\) to \(10^6\) from west to east, and the dinosaur camp is located to the west of tree \(1\). For \(n\) days, on day \(i\) the dinosaur walks from the camp to tree \(a_i\) and then returns. On the way to tree \(a_i\), she picks \(v_i\) leaves from every tree she encounters. Note that during a single day, each tree is visited at most once, so each tree loses leaves at most once per day.

Initially, \(v_i = 0\) for every day \(i\). Then there are \(m\) modifications. In the \(j\)th modification, the value \(v_i\) for every day \(i\) with \(1 \le i \le p_j\) is increased by \(w_j\). These modifications take effect for all subsequent queries.

There are also \(z\) queries. In the \(j\)th query, given two numbers \(p_j\) and \(d_j\), you are required to calculate the total number of leaves picked from tree \(d_j\) during the first \(p_j\) days, i.e. the sum of \(v_i\) for all days \(i \le p_j\) with the property that tree \(a_i \ge d_j\) (since the dinosaur only picks leaves from trees on her way to tree \(a_i\)).

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(n\), \(m\), and \(z\) separated by spaces.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)), representing the destination tree on day \(i\).

The next \(m\) lines each contain two integers \(p_j\) and \(w_j\) describing a modification: for all days \(i\) with \(1 \le i \le p_j\), increase \(v_i\) by \(w_j\).

The following \(z\) lines each contain two integers \(p_j\) and \(d_j\) describing a query: for the first \(p_j\) days, output the total number of leaves picked from tree \(d_j\).

outputFormat

For each query, output a single integer, which is the total number of leaves picked from the queried tree over the specified days.

sample

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

8
9
4