Migrated from Lutece 3131 你好，所以，再见～

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

请注意，本题不计一血。

Tag：线段树/树状数组/分块/……

欢迎各位前来参加本次暑假前集训。本次专题为数据结构专场，希望您在本次专题中玩的愉快。

所以，我要睡觉了，这道题就你来帮我写了吧。

---

lh3k 有一个长度为 $n\ (1\le n\le 10^6)$ 的序列 $\lbrace a_i\rbrace$，初始时序列中所有元素均为零，即 $\forall k=1, 2,\dots,n,\ a_k=0$。现在 lh3k 要在这个序列上进行 $q\ (1\le q\le 10^6)$ 次操作。具体而言，有以下两种操作：

1. 给出一个区间 $[l,r]\ (1\le l\le r\le n)$ 及一个增量 $x\ (|x|\le 10^6)$，在序列在区间 $[l,r]$ 中的数都加上 $x$，即令 $\forall k=l, l+1,\dots,r,\ a_k:=a_k+x$；
2. 给出一个区间 $[l,r]$，询问序列在区间 $[l,r]\ (1\le l\le r\le n)$ 中所有的数的和，即输出 $\sum\limits_{k=l}^ra_k$。

你能帮 lh3k 解决这个问题吗？

Input

输入数据的第一行包含两个数 $n$ 和 $q\ (1\le n, q\le 10^6)$，表示序列的长度和操作次数。

接下来的 $q$ 行每行包含 $3$ 至 $4$ 个整数，形式如下：

1. 1 l r x，表示将序列在区间 $[l, r]\ (1\le l\le r\le n)$ 中的数都加上 $x\ (|x|\le10^6)$；
2. 2 l r，表示询问序列在区间 $[l,r]\ (1\le l\le r\le n)$ 中所有的数的和。

输入数据保证至少有一次询问操作。

Output

对于每一次询问，输出一行一个整数，表示询问的结果。

Samples

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

3
24

10 10
1 3 4 2
2 3 4
1 4 5 2
1 8 9 9
1 2 7 4
1 7 10 3
1 3 4 4
1 6 9 1
1 5 9 8
2 1 10

4
114

Constraints

$1\le n, q\le 10^6$

对于区间加操作，$1\le l\le r\le n$，$|x|\le 10^6$

对于修改操作，$1\le l\le r\le n$

保证至少有一次询问操作。

Note

你可能需要比较快的输入输出方式。

Resources

2024 UESTC ICPC Training for Data Structure