题目描述

给定数列$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，表示数列长度和询问个数。保证$1 \le n,q \le10^6$。 第二行n个整数$a[1],a[2], \dots,a[n]$，表示初始数列。保证$|a[i]| \le10^6$。 接下来q行，每行一个操作，为以下两种之一： 1 l r x：对于所有$i \in[l,r]$，将a[i]加上x； 2 l r：输出$\sum_{i=l}^ra[i]$的值。保证$1 \le l \le r \le n,$ $|x| \le10^6$。

输出描述

对于每个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

备注

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