题目背景

容易发现，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$			无
$\operatorname{Subtask}2$	$10$		无特殊限制	无特殊限制	无特殊限制	AB
$\operatorname{Subtask}3$	$15$	$5$				B
$\operatorname{Subtask}4$		$1$		$=1$		C
$\operatorname{Subtask}5$						无
$\operatorname{Subtask}6$	$20$	$4$		$\le 50$
$\operatorname{Subtask}7$		$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}$ 对本题的贡献！