题目描述

给定数列$a[1],a[2], \dots,a[n]$，你需要依次进行q个操作，操作有两类：

1 l r x：给定l,r,x，对于所有$i \in[l,r]$，将a[i]加上x（换言之，将$a[l],a[l+1], \dots,a[r]$分别加上x）；

2 l r：给定l,r，求$\sum_{i=l}^ra[i]$的值（换言之，求$a[l]+a[l+1]+ \dots+a[r]$的值）。

输入描述

第一行包含2个正整数n,q，表示数列长度和询问个数。 第二行n个整数$a[1],a[2], \dots,a[n]$，表示初始数列。 接下来q行，每行一个操作，为以下两种之一： 1 l r x：对于所有$i \in[l,r]$，将a[i]加上x； 2 l r：输出$\sum_{i=l}^ra[i]$的值。

输出描述

对于每个2lr操作，输出一行，每行有一个整数，表示所求的结果。

示例1

输入

5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4

输出

15
34
32
33
50

备注

输入样例 #2

2 7
1000000 -1000000
2 1 1
2 2 2
1 1 1 -8796
1 1 1 2947
2 2 2
1 2 2 -1210
1 2 2 4143

输出样例 #2

1000000
-1000000
-1000000

输入样例 #3

7 7
1000000 -1000000 -1000000 1000000 -1000000 541302 -1000000
2 5 6
1 5 5 -1221
2 6 6
1 1 1 376
1 2 5 8680
1 1 1 -4362
2 4 4

输出样例 #3

-458698
541302
1008680

数据范围

对于所有数据，$1 \le n,q \le10^6,$ $|a[i]| \le10^6$,$1 \le l \le r \le n,$ $|x| \le10^6$。

保证$1 \le n,q \le10^6$。

保证$|a[i]| \le10^6$。

保证$1 \le l \le r \le n,$ $|x| \le10^6$。