No testdata at current.

题目背景

小 X 闲来无事，决定做两道题。

但这时他突然发现——机房的电脑居然被小 Y 入侵了！

题目描述

小 X 的机房里有 $n$ 台电脑，每台电脑都有一个防御指数 $d_i$。

同时，小 Y 还可以使用技能攻击，将 $[l,r]$ 区间内所有电脑的防御指数减少 $k$。

但是小 X 会使用防火墙，可以将 $[l,r]$ 区间内所有电脑的防御指数加上一个首项为 $k$，公差为 $d$ 的等差数列。

现在小 Y 给了你一些问题，他想知道某些区间内防御指数之和是多少？

输入格式

第一行有两个数 $n$ 和 $m$，表示有 $n$ 台电脑和 $m$ 次操作。

第二行有 $n$ 个数，表示每台电脑最开始时的防御指数 $d_i$。

接下来 $m$ 行，每行最前面有一个数 $op$：

若 $op=1$，输入三个整数 $l,r,k$，表示将 $[l,r]$ 区间内所有电脑的 $d_i$ 减少k；

若 $op=2$，输入四个整数 $l,r,k,p$，表示将 $[l,r]$ 区间内所有电脑的 $d_i$ 加上一个首项为 k，公差为 p 的等差数列；

若 $op=3$，输入两个正整数 $l,r$，表示询问 $[l,r]$ 区间内 $d_i$ 之和。

输出格式

对于每次询问，输出一行一个整数表示答案。

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

4
18

样例解释

在执行完第一个操作后，所有电脑的防御指数变为：1 1 2 3 4

此时 $[1,3]$ 区间 $d_i$ 之和为 $4$。

在执行完第三个操作后，所有电脑的防御指数变为：1 2 4 6 8

此时 $[3,5]$ 区间 $d_i$ 之和为 $18$

数据规模与约定

$1\le n,m\le 10^5$

$0\le d_i\le 2\times10^3$

$1\le l,r\le n$