P7922 [Kubic] Pyramid

It is easy to see that the setter of Problem F is not lxl. 

You are given a sequence $p$ with initial length $n$. Let the current length of $p$ be $L$. There are two kinds of operations: - Operation A first constructs a sequence $p'$ of length $L-1$ such that $p_i'=\min\{p_i,p_{i+1}\},i\in [1,L)$. Then replace $p$ with $p'$. - Operation B first constructs a sequence $p'$ of length $L-1$ such that $p_i'=\max\{p_i,p_{i+1}\},i\in [1,L)$. Then replace $p$ with $p'$. You are also given a sequence $a$ of length $m$, meaning there are $m$ groups of operations. In the $i$-th group, perform $a_i$ times operation A first, and then perform $a_i$ times operation B. It is guaranteed that $2\sum a_i=n-1$. Finally, you are given $q$ queries. Each query provides parameters $x,l,r$. You need to compute the value of $\sum\limits_{i=l}^r p_i$ after the first $x$ operations. **Note: in the queries, $x$ means the first $x$ operations, not the first $x$ groups of operations. That is, a query may happen in the middle of some group of operations.**

The first line contains three integers $n,m,q$. The second line contains $n$ integers, where the $i$-th integer denotes $p_i$. The third line contains $m$ integers, where the $i$-th integer denotes $a_i$. The next $q$ lines each contain three integers $x,l,r$, representing one query.

Output $q$ lines. Each line contains one integer. The integer on the $i$-th line is the answer to the $i$-th query.

For $100\%$ of the data, $1\le n,m,q\le 1.5\times 10^5,1\le x