3322. [模板]可持久化线段树2

【题目描述】

给定一个长度为$n$的整数序列$a$，为第$0$版，然后执行$m$次操作：

0 l r x，表示产生一个新版本，然后将区间$[l,r]$中的每个数增加$x$。

1 k l r，表示查询第$k$个版本中$a[l,r]$的和。

【输入格式】

第一行一个正整数$n$，表示序列$a$的大小，一个正整数$m$，表示$m$次操作。

第二行包含$n$个整数，表示序列$a$。

接下来$m$行，每行一个操作，具体格式参考【题目描述】。

【输出格式】

对于每个查询操作，输出一行一个整数表示答案。

【样例输入】

5 8
1 9 1 10 3
0 2 5 4
0 3 4 1
1 2 1 2
1 2 3 4
1 1 3 4
0 2 4 5
0 4 5 4
1 4 1 5

【样例输出】

14
21
19
65

【数据规模与约定】

$1\leq n, m\leq 10^5,|a[i]|,|x|\leq 10^6$，保证$1\leq k\leq $已经存在的版本。