题目描述

有 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成一个序列。有一个存储三元组的列表，开始时该列表为空。
有 $m$ 个操作，这些操作分为两种：

• $\texttt{1 L R x}\:\:$ 将 $(L, R, x)$ 加入列表中。
• $\texttt{2 L R}\;\;\quad$ 求 $aL + a{L+1} + \cdots + a_R$。

每执行完一个操作，就读取一遍列表，对于其中的每一组 $(L, R, x)$，$aL, a{L+1},\ldots,a_R$ 都加上 $x$（这不算做操作）。

输入格式

第一行一个整数 $n$，表示序列长度。
第二行 $n$ 个整数。
第三行一个整数 $m$，表示操作数。
然后 $m$ 行，先输入一个数 $D$，$D$ 为 $1$ 或 $2$ 。

• 若 $D$ 为 $1$，读入 $3$ 个整数 $L, R, x$。
• 若 $D$ 为 $2$，读入 $2$ 个整数 $L, R$。

输出格式

对于每个操作 $\texttt{2 L R}$，输出一行，一个整数，$aL + a{L+1} + \cdots + a_R$ 。

样例

input

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

output

2
15

数据范围与提示

对于 $ 60 \% $ 的数据，暴力可过。
对于 $ 100 \% $ 的数据，$ 1 \le n, m \le 10^5, $ $ 1 \le L \le R \le n, $ $ 1 \le a_i \le 10^4 $, $ -10^4 \le x \le 10^4 $。