题目描述

有 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成一个序列。有一个存储三元组的列表，开始时该列表为空。

有 $m$ 个操作，这些操作分为两种：

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

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

输入格式

第一行一个整数 $n$，表示序列长度。
第二行 $n$ 个整数，表示初始序列 $a_1, a_2, \dots, a_n$。
第三行一个整数 $m$，表示操作数。
接下来 $m$ 行，每行先输入一个数 $D$（$D$ 为 1 或 2）：

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

输出格式

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

样例

输入

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

输出

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