背景

注意：本题最后有形式化题意（内含具体描述），请注意。

自【方舟】返回之后，sensei一直在关注白子【色彩】，但后者似乎一直在躲着sensei。

实在放心不下的sensei找到了日鞠。

一会儿之后，日鞠发现，白子【色彩】是白子在另一时间线上的其他可能性，其一切可能性均可以由现在世界线上的白子与那条时间线上的sensei，即【诱骗者】，推演而来。

具体地，白子的信息与【诱骗者】的信息均可以抽象为长度为一相同定值的整数序列，二者对应位置上的数的乘积即为对应位置上白子【色彩】的信息的抽象形式。

于是sensei找来了白子，并提供了【诱骗者】所留下的信用卡用以信息解析。

白子非常愿意配合，【诱骗者】的信用卡也已经找到了分析信息的方式。但是，仍然有一些细枝末节的问题：由于时间是流动的，白子的行动不可能一成不变，因此有时需要更新信息；而解析的【诱骗者】的信息也会不断更新，抽象在序列上，二者的更新方式均为数值加上某一个定值，而由于单位的信息意义不大，因此信息的更新总是对一个连续区间进行，即对序列的某一个闭合子区间全部加上一个整数；

同时，sensei也需要在一些时刻获得目前已有的白子【色彩】的信息，由于前面说过，单位的信息意义不大，因此sensei获取的信息也一定是一个连续段的信息，即一个闭合子区间内的上述两个序列的对应位置的积的和。

由于是细枝末节的小事，日鞠就顺手把这项维护两个序列信息的程序的编写任务扔到了某个委托网站上。恰好，便利屋68的社长———陆八魔爱露，在不知道为什么便利屋又一次陷入财政赤字的窘境下盯上了这一委托，但便利屋没人会这活，于是她们把你绑架来干活。

Description

给定两个长度为 $n+1$ 的数组 $a,b$，初始时其中元素全部为 $0$，您需要维护以下三种操作：

1 l r： 查询 $\sum_{i=l}^{i\le r} a_ib_i$。

2 l r v：$\forall i \in [l,r],a_i\leftarrow a_i+v$。

3 l r v：$\forall i \in [l,r],b_i\leftarrow b_i+v$。

操作共 $q$ 次。注意，数组的初始下标是 $0$。

Format

Input

从shiroko.in读入测试数据。

第一行两个整数 $n,q$ 含义见题目描述。

接下来 $q$ 行每行有 $3$ 到 $4$ 个以空格隔开的整数：

1 l r 或 2 l r v 或 3 l r v，含义见题目描述，保证 $0 \le l \le r \le n,-10^6 \le v \le 10^6$。

Output

输出到shiroko.out中。

对于每个操作 1 输出一行一个整数表示本次询问答案。

Samples

7 12
2 0 1 -1
2 1 1 -1
1 2 6
3 2 5 -1
1 0 4
1 3 6
2 0 4 2
3 0 6 -6
3 3 6 2
1 1 5
2 1 3 5
3 2 2 4

0
0
0
-34

15 20
2 2 12 -2
2 5 14 -2
1 1 4
3 5 14 -4
1 3 13
1 5 10
2 0 6 5
3 0 14 -4
3 4 9 1
1 1 7
2 4 14 9
3 4 8 5
3 6 11 -8
1 1 3
2 10 11 3
1 9 12
1 4 8
3 6 10 5
3 8 13 5
2 3 7 -6

0
136
96
-39
-44
-371
-196

20 30
2 2 12 -2
2 5 14 -12
1 4 11
3 5 9 -14
1 3 18
1 5 15
2 0 6 5
3 0 19 -4
3 4 19 1
1 6 17
2 9 9 14
3 3 19 5
3 6 6 -3
1 13 16
2 0 11 13
1 9 12
1 9 18
3 6 15 10
3 13 13 5
2 7 8 -6
2 4 6 -14
1 0 15
3 16 17 9
1 5 14
1 2 7
2 13 18 -4
2 0 6 7
3 2 6 -1
1 7 16
1 6 14

0
980
980
1065
-48
-188
-236
-556
-368
140
-746
-636

见附加文件shiroko4.in

见附加文件shiroko4.ans

样例 $4$ 满足 $n=q=4\times 10^4,-1.5 \times -10^4 \le v \le 1.5 \times -10^4$。

见附加文件shiroko5.in

见附加文件shiroko5.ans

样例 $5$ 满足 $n=q=4\times 10^5, -10^6 \le v \le 10^6$。

Limitation

对于全部的测试数据，满足 $n,q\le 6\times 10^5,0 \le l \le r \le n,-10^6 \le v \le 10^6$。

各数据点约束：

测试点编号	$n\le$	$q\le$	${v\ge}$	$v\le$	测试点分值
$1-3$	$50$		$-50$	$50$	$1$
$4$	$100$
$5-6$	$500$		$-100$	$100$
$7-8$	$1000$		$-10^3$	$10^3$
$9-10$	$5000$
$11-15$	$10^4$		$-10^4$	$10^4$	$2$
$16-17$	$2\times 10^4$
$18-20$	$3\times 10^4$
$21-25$	$5\times 10^4$
$26-30$			$-5\times 10^4$	$5\times 10^4$
$31-35$	$10^5$				$3$
$36-37$			$-10^5$	$10^5$
$38-39$	$2\times 10^5$				$4$
$40-41$	$4\times 10^5$		$-10^6$	$10^6$
$42$	$6\times 10^5$	$6\times 10^5$			$8$
$43$		$3.5\times 10^5$	$-5\times 10^5$	$5\times 10^5$	$5$

测试点 $38-41$ 时限 $2.5s$，$42$ 时限 $7.5s$，测试点 $43$ 时限 $5.5s$，其余测试点时限 $1s$。

本题输入输出量极大，请自备较快的I/O方式以及注意常数。

Written by itoshiki_Treap