Background

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

Problem Description

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.

Input Format

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 Format

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

5 2 3
6 2 4 1 3
1 1
1 1 4
2 2 3
4 1 1

6
3
2

Hint

For $100\%$ of the data, $1\le n,m,q\le 1.5\times 10^5,1\le x<n,1\le l\le r\le n-x,1\le p_i\le 10^9,2\sum a_i=n-1$.

Special Property A: $\forall i,a_i=1$.

Special Property B: $l=r$.

Special Property C: $l=1,r=n-x$.

Sample Explanation

The given operation process is as follows:

6 2 4 1 3

2 2 1 1

2 2 1

2 1

2

Writing special properties separately is only to make the table look nicer...

Thanks to $\operatorname{A\color{red}lfalfa\_w}$ for contributing to this problem!

Translated by ChatGPT 5