题目描述

这是一道模板题。

给定数列$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}^r a[i]$ 的值（换言之，求$a[l]+a[l+1]+\cdots+a[r]$ 的值）。

输入

第一行包含 2 个正整数$n,q$，表示数列长度和询问个数。保证$1 \leq n,q \leq 10^6$ 。

第二行$n$ 个整数$a[1],a[2],\dots,a[n]$，表示初始数列。保证$|a[i]| \leq 10^6$ 。

接下来$q$ 行，每行一个操作，为以下两种之一：

1.$l\ r\ x$：对于所有$i \in [l,r]$，将$a[i]$ 加上$x$；

2.$l\ r$：输出$\sum_{i=l}^r a[i]$ 的值。

保证$1 \leq l \leq r \leq n, |x| \leq 10^6$ 。

输出

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

样例

输入样例 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

输出样例 1

15
34
32
33
50

提示

数据范围与提示：

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

来源

一本通在线评测