题目背景

周六午睡时想的。

笑死，喝了半杯咖啡，根本睡不着。

题目描述

线段树模板，不多赘述。

输入格式

第一行两个整数$n$，$m$，分别是序列长度和询问次数。

第二行$n$个整数$a_i$。

接下来$n$行，需要执行两种操作：

1 l r c

将区间$[l,r]$中所有数加上$c$。

2 l r

求出$[l,r]$内的和。

输出格式

对于每一个2号操作，输出一个整数。

要换行。

输入样例

输入

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

输出

11
8
20

数据范围

对于所有数据，$1≤a_i≤10^6$，保证所有数据不超过$long$ $long$的范围。

说明

内存$512MB$，时间限制$1s$。