题目描述

这是一道模板题。

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

• 1 l r x： 对$a[l]，a[l+1],\dots , a[r]$ 区间的数字分别加上一个数字x。

• 2 l r： 给定l, r, 求数组出区间[l, r]的和， 也就是$a[l]+a[l+1]+,\dots , +a[r]$

输入格式

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

第二行 n 个整数$a[1], a[2], ...... a[n]$表示初始数列。保证 $| a[i]| \leq 10^6$ 。 接下来 行，每行一个操作，为两种操作之一。

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

输出格式

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

输入输出样例 #1

输入 #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