题目背景

如今，这位饱经风霜的骑士只剩下空洞的自尊。

在《脑叶公司》中的 WAW 级异想体绝望骑士（O-01-73），曾为“正义魔法少女”。她立志守护众人，却眼见身边之人逐一堕入黑暗，往昔的良善消失殆尽，最终陷入了无尽的绝望，认定自己未能守护好他人。

• 逆卡巴拉计数器：每天第一位以优秀结果完成对绝望骑士工作的员工，将获得“绝望骑士的祝福”。得到祝福的员工不能再进行任何工作，只能用于镇压出逃的异想体。因骑士的祝福，员工受到的红、白、黑伤减半，但蓝伤会变为原来的两倍。当被祝福的员工死亡或陷入恐慌，“绝望骑士”给予的祝福消失，同时“绝望骑士”将会突破收容。
• 攻击特性：绝望骑士突破收容后，会在设施内随机移动。每次移动后，一般会进行 $2\sim3$ 次攻击，约 $50\%$ 为蓝伤，若被没有蓝抗的员工撞上，会有生命危险。

题目描述

绝望骑士的存在会引发周围空间产生特殊的能量波动。

这些能量波动可以用一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$ 来表示，每个元素 $a_i$ 代表着对应位置的能量强度。

为了控制绝望骑士的力量，公司研发了一种特殊的装置，该装置可以对能量波动序列进行调整。每次操作可以选择一个区间 $[l,r]$，并将该区间内的每个元素都加上一个给定的值 $x$。同时，为了监测调整效果，需要进行一些查询操作。查询操作是询问在经过一系列调整后，某个区间 $[l,r]$ 内所有元素的和。

你作为主管，任务是处理一系列的调整操作和查询操作，并输出每次查询操作的结果。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示能量波动序列的长度和操作的总次数。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示初始的能量波动序列。

接下来 $m$ 行，每行表示一个操作：

• 1 l r x：将区间 $[l,r]$ 内的每个元素都加上 $x$。
• 2 l r：查询在经过一系列调整后，区间 $[l,r]$ 内所有元素的和。

输出格式

对于每个操作 $2$，输出一行一个整数，表示查询区间内所有元素的和。

输入输出样例

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

8
17

说明 / 提示

样例解释

0. $[1,2,3,4,5]$。
1. $[1,3,4,5,5]$。
2. $1+3+4=8$。
3. $3+4+5+5=17$。

数据范围与约定

对于 $100\%$ 的数据，$1 \le n \le 10^5,1 \le m \le 100,1 \le a_i \le 1000$。