题目描述

流动图书车上的书按顺序排成一列，每本书都有一个页数。管理员会进行三种操作：

• 1 p x：在当前第 $p$ 本书前插入一本页数为 $x$ 的新书；
• 2 p：移走当前第 $p$ 本书；
• 3 l r：询问当前第 $l$ 本到第 $r$ 本书的页数之和。

请你依次处理所有操作，并对每个询问输出答案。

保证所有操作都是合法的。

输入格式

第一行两个整数 $n,m$，分别表示初始书本数量和操作数量。

第二行 $n$ 个整数，表示每本书的页数。

接下来 $m$ 行，每行一个操作，格式见题目描述。

输出格式

对于每个询问操作 3 l r，输出一行答案。

4 5
10 20 30 40
3 2 4
1 3 15
2 5
3 1 3
3 2 4

90
45
65

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m \le 2000$，页数与答案均在 64 位有符号整数范围内。