Sequence Reduction Queries

You are given an initial sequence \(p\) of length \(n\). Two types of operations can be performed on this sequence while its current length is \(L\):

• Operation A: Construct a new sequence \(p'\) of length \(L-1\) where \(p'_i=\min\{p_i, p_{i+1}\}\) for \(i\in [1,L-1]\), and then replace \(p\) with \(p'\).
• Operation B: Construct a new sequence \(p'\) of length \(L-1\) where \(p'_i=\max\{p_i, p_{i+1}\}\) for \(i\in [1,L-1]\), and then replace \(p\) with \(p'\).

You are also given a sequence \(a\) of length \(m\). The whole process consists of \(m\) groups of operations. In the \(i\)-th group, you first perform \(a_i\) consecutive A operations and then \(a_i\) consecutive B operations. It is guaranteed that \[ 2\sum_{i=1}^{m}a_i = n-1. \]

Finally, there are \(q\) queries. Each query gives three integers \(x, l, r\). The integer \(x\) represents the number of operations (not groups) performed from the beginning. (Note that queries might be issued when a group is partially completed.) After performing the first \(x\) operations, let the current sequence be \(p\). You are to answer the sum of the elements from index \(l\) to \(r\) (1-indexed) of \(p\).

Input/Output Formats are described below.

inputFormat

The first line contains three integers \(n, m, q\) (the initial length of the sequence, the number of operation groups, and the number of queries).

The second line contains \(n\) integers \(p_1, p_2, \dots, p_n\), representing the initial sequence.

The third line contains \(m\) integers \(a_1, a_2, \dots, a_m\). It is guaranteed that \(2\sum_{i=1}^{m} a_i = n-1\).

Each of the next \(q\) lines contains three integers \(x, l, r\) representing a query. Here, \(x\) is the number of operations performed from the start, and \(l, r\) are the indices (1-indexed) defining the range for which you need to find the sum in the current sequence.

outputFormat

For each query, output a single integer representing the sum of the elements from index \(l\) to \(r\) after performing the first \(x\) operations.

sample

5 2 4
3 1 2 4 5
1 1
0 1 5
2 2 3
3 1 1
4 1 1

15
6
1
2