[Kubic] Pyramid

容易发现，F 题出题人不是 lxl。 

给定一个初始长度为 $n$ 的序列 $p$。 设当前 $p$ 的长度为 $L$，有以下两种操作： - A 操作先构造长度为 $L-1$ 的序列 $p'$ 满足 $p_i'=\min\{p_i,p_{i+1}\},i\in [1,L)$。然后用 $p'$ 代替 $p$。 - B 操作先构造长度为 $L-1$ 的序列 $p'$ 满足 $p_i'=\max\{p_i,p_{i+1}\},i\in [1,L)$。然后用 $p'$ 代替 $p$。 再给定一个长度为 $m$ 的序列 $a$，表示一共进行 $m$ 组操作，第 $i$ 组中先进行 $a_i$ 次 A 操作，再进行 $a_i$ 次 B 操作。保证 $2\sum a_i=n-1$。 最后给定 $q$ 次询问，每次给出参数 $x,l,r$，你需要求出进行前 $x$ 个操作之后 $\sum\limits_{i=l}^r p_i$ 的值。 **注意：询问中的 $x$ 指的是前 $x$ 个操作而不是前 $x$ 组操作，即有可能在某一组操作进行一部分时询问。**

第一行，三个整数 $n,m,q$。 第二行，$n$ 个整数，第 $i$ 个整数表示 $p_i$。 第三行，$m$ 个整数，第 $i$ 个整数表示 $a_i$。 接下来 $q$ 行，每行三个整数 $x,l,r$，表示一次询问。

共 $q$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 次询问的答案。

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

6
3
2

对于 $100\%$ 的数据，$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$。 ||分值|时限 $(\operatorname{s})$|$n$|$m$|$q$|特殊性质| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$\operatorname{Subtask}1$|$5$|$1$|$\le 100$|$\le 100$|$\le 100$|无| |$\operatorname{Subtask}2$|$10$|$1$|无特殊限制|无特殊限制|无特殊限制|AB| |$\operatorname{Subtask}3$|$15$|$5$|无特殊限制|无特殊限制|无特殊限制|B| |$\operatorname{Subtask}4$|$15$|$1$|无特殊限制|$=1$|无特殊限制|C| |$\operatorname{Subtask}5$|$15$|$1$|无特殊限制|$=1$|无特殊限制|无| |$\operatorname{Subtask}6$|$20$|$4$|无特殊限制|$\le 50$|无特殊限制|无| |$\operatorname{Subtask}7$|$20$|$5$|无特殊限制|无特殊限制|无特殊限制|无| 特殊性质 A：$\forall i,a_i=1$ 特殊性质 B：$l=r$。 特殊性质 C：$l=1,r=n-x$。 ### 样例解释 给定的操作过程如下： `6 2 4 1 3` `2 2 1 1` `2 2 1` `2 1` `2` ~~特殊性质单独拉出来写只是为了表格好看一点...~~ 感谢 $\operatorname{A\color{red}lfalfa\_w}$ 对本题的贡献！