给定一个长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$。请编写程序执行以下查询：

• 1 L R X：对所有 $L \le i \le R$，令 $A_i = A_i + X$。
• 2 L R S E：将 $A$ 的 $[L, R]$ 区间修改为 $[S, E]$ 中的数。即，设此查询的结果序列为 $B$，则有 $B_L = A_S, B_{L+1} = A_{S+1}, \ldots, B_R = A_E$，且对于所有不在 $L \le i \le R$ 中的 $i$，$B_i = A_i$。
• 3 L R：输出 $A_L + A_{L+1} + \ldots + A_R$。

输入格式

第一行包含一个整数 $N$，表示序列的长度。（$1 \le N \le 200{,}000$）

第二行包含 $A_1, A_2, \ldots, A_N$。（$-10^6 \le A_i \le 10^6$）

第三行包含一个整数 $M$，表示查询的个数。（$1 \le M \le 200{,}000$）

接下来的 $M$ 行，每行描述一个查询。（$1 \le L \le R \le N$，$1 \le S \le E \le N$，$E-S = R-L$，$-10^6 \le X \le 10^6$）其中至少有一个类型 3 的查询。

输出格式

对于每个类型 3 的查询，输出一行，包含相应的和。

样例

样例输入 1

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

样例输出 1

15
9
20