题目背景

翻译自 CSES-1737 题。

题目描述

你的任务是维护一个数组列表，初始时该列表只有一个数组。你需要处理以下几种类型的查询：

1. 将数组 $k$ 中位置 $a$ 的值设为 $x$。
2. 计算数组 $k$ 中区间 $[a,b]$ 的值的和。
3. 创建数组 $k$ 的副本，并将其添加到数组列表的末尾。

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示数组的大小和查询的数量。

第二行包含 $n$ 个整数 $t_1,t_2,…,t_n$：表示数组的初始内容。

接下来有 $q$ 行，每行描述一个查询。查询的格式有三种：

• 1 k a x：表示将数组 $k$ 中位置 $a$ 的值设为 $x$。
• 2 k a b：表示计算数组 $k$ 中区间 $[a,b]$ 的值的和。
• 3 k：表示创建数组 $k$ 的副本，并将其添加到列表末尾。

输出格式

对于每个类型为 2 的查询，输出该区间内的值的和。

样例

5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5

13
13
13
15

说明/提示

$1 \leq n,q \leq 2 \cdot 10^5$；

$1 \leq t_i,x \leq 10^9$；

$1 \leq a \leq b \leq n$。