题目描述

给定一个长度为$n$的序列：$A_1,A_2......A_n$，对它进行$m$次操作：

$1.$输入$1$ $x$ $y$ $z$，表示把$A_x$到$A_y$都加上$z$。

$2.$输入$2$ $l$ $r$，求出$\sum_{i=l}^rA_i$。

输入

第一行输入一个整数$n$，表示序列$A$的长度。

第二行输入$n$个数，分别是$A_1,A_2......A_n$。

第三行输入一个整数$m$，表示操作的次数。

第$4$到$3+m$行，输入$m$次操作。

输出

对于每个操作$2$，输出一行，为$\sum_{i=l}^rA_i$。

样例数据

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

10
15

数据范围

$0<n,m,x,y,l,r\le10^6$

$-10^9\le A_i,z\le10^9$