时空限制

2S/512M

题目描述

apiadu 是一个伟大的收藏家，他把他的所有收藏都放到了一个长桌子上，这个桌子最多能放 $n$ 个收藏，收藏会从左到右依次摆放。初始时，桌子摆满了 $n$ 个收藏，第 $i$ 个收藏的价值为 $a_i$。

你需要处理 $q$ 次操作，每个操作为以下三种类型之一：

1. 给定整数 $k,x,v$。apiadu 获得了 $x$ 个价值为 $v$ 的新收藏，他把它们插入到桌子上的第 $k$ 个收藏与第 $k+1$ 个收藏之间（特别地，如果 $k=0$，则插入在所有收藏之前；如果 $k=n$，则插入在所有收藏之后）。由于桌子只能容纳 $n$ 个收藏，因此插入后的第 $n+1$ 至第 $n+x$ 个收藏会被 apiadu 卖掉，apiadu 会查询卖掉的收藏的总价值是多少。
2. 给定整数 $l,r,v$。桌子上的第 $l$ 个到第 $r$ 个收藏价值分别增加 $v$。
3. 给定整数 $l,r$。apiadu 查询桌子上的第 $l$ 个到第 $r$ 个收藏的价值总和是多少。

对于每个类型 $1$ 和类型 $3$ 的操作，请你帮 apiadu 算出他查询的答案。

格式

输入格式

第一行包含一个整数 $c$，表示该测试点所属子任务编号，$c = 0$ 表示该测试点为样例。

第二行包含两个整数 $n,q$，表示桌子容量和操作个数。

第三行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示初始时桌子上的每个收藏的价值。

接下来 $q$ 行，每行表示一个操作。每个操作先输入一个整数表示操作类型，三种类型的操作分别按如下格式给出：

1 k x v 给定整数 $k,x,v$，表示类型 $1$ 的操作。

2 l r v 给定整数 $l,r,v$，表示类型 $2$ 的操作。

3 l r 给定整数 $l,r$，表示类型 $3$ 的操作。

输出格式

对于每个类型 $1$ 和类型 $3$ 的操作，输出一行一个整数表示查询的答案。

样例

样例输入 #1

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

样例输出 #1

8
14
21

样例解释 #1

下图为收藏的变化示意图

样例输入 #2

0
4 3
1 5 1 10
1 0 3 3
2 2 4 7
1 3 4 6

样例输出 #2

16
26

样例解释 #2

下图为收藏的变化示意图

样例输入 #3

0
10 7
4 5 1 12 1 10 8 4 14 8
2 5 8 1
2 6 10 4
1 10 7 10
3 2 7
1 7 8 12
2 4 9 13
3 9 9

样例输出 #3

70
48
99
25

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于所有测试点，均有：

• $1 \le n,q \le 2 \times 10^5$。

• 对于所有 $1 \le i \le n$，均有 $1 \le a_i \le 10^9$。

• 对于所有类型 $1$ 的操作，均有 $0 \le k \le n$，$1 \le x \le n$，$1 \le v \le 10^9$。

• 对于所有类型 $2$ 的操作，均有 $1 \le l \le r \le n$，$1 \le v \le 10^7$。

• 对于所有类型 $3$ 的操作，均有 $1 \le l \le r \le n$。

子任务编号	分数	$n,q \le$	特殊性质
$1$	$10$	$3000$	无
$2$	$12$	$2 \times 10^5$	A
$3$	$10$		BC
$4$	$10$		B
$5$	$18$		C
$6$	$40$		无

特殊性质 A：只包含类型 $2$ 和类型 $3$ 的操作。

特殊性质 B：对于所有类型 $1$ 的操作，均有 $k=0$。

特殊性质 C：对于所有类型 $1$ 的操作，均有 $x \le 5$。