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.

Description

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

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

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

Format

Input

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

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

Output

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

Samples

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

2
15

Limitation

对于 $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$。