You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

线段树（$\texttt{segt}$）

【题目描述】

露娜喜欢线段树。

露娜正在做线段树模板题，题目给定了 $n$ 个整数 $a_1,a_2,\dots,a_n$，并顺序给出 $m$ 个操作 $P_1,P_2,\dots,P_m$，形如：

• 修改操作：形如 1 l r x 表示把 $a_l\sim a_r$ 加上 $x$。
• 查询操作：形如 2 l r：表示求 $a_l\sim a_r$ 的区间和。

露娜觉得这太简单了，于是她想到了这样一个问题：假如我依次执行 $P_x,P_{x+1},\dots,P_y$ 这些操作，那么这些操作中所有查询操作的得到答案的总和是多少？

但露娜觉得这依然太简单了，所以她一口气想出了 $q$ 组这样的 $x,y$，她想对每组这样的 $x,y$ 求出答案。

注意：所有的操作都是在露娜的脑海里进行的，并不会对后面的询问产生影响（即询问之间互相独立）。

露娜并不会做这题，你可以帮她做出这道题吗？

【输入格式】

从 $\texttt{segt.in}$ 中读入数据。

一行三个正整数 $n,m,q$，含义如题。

第二行 $n$ 个正整数，第 $i$ 个表示 $a_i$，含义如题。

接下来 $m$ 行，每行形如 1 l r x 或 2 l r，第 $i$ 行表示第 $i$ 个操作。

接下来 $q$ 行，每行两个整数 $x,y$，表示一次询问。

【输出格式】

输出到 $\texttt{segt.out}$ 中。

输出 $q$ 行，每行一个整数表示答案。

【样例 1 输入】

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

【样例 1 输出】

6
29
0
20
72

【数据范围】

所有测试数据满足：$n,m,q\le 2\times 10^5,-10^3\le a_i,x\le 10^3$。