Migrated from Lutece 2947 Stack Rearrange

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

继 $Stack \ Merge$ 题之后，我们可以预见的是，在有限次 $Merge$ 操作后，所有的栈最终会排列在一个容器里，形成一个自顶向下的序列。在这里，我们将这个序列重新标号，自顶向下序号分别为 $1...n$ 。

前面未提到的是， $S$ 国内容器内装载的每一个元素都有一个价值 $value$ 。即每个元素实际上有两个属性——序号与价值，其中序号并不随着元素位置的变化而变化，且初始每个元素的序号就等于元素的位置。为了支持 $S$ 国的建设，$S$ 国聘请了”管理员“。管理员有以下几种操作：

1. 把序号为 $x$ 的元素放在序号为 $y$ 的元素的前面，保证 $x,y$ 不相等。例如我们现在有初始排列 $1,2,3,4,5$ ，$x=2,\ y=5$ ，则排列变为 $1,3,4,2,5$ 。
2. 将序号为 $x$ 的元素对应的 $value$ 改为 $y$
3. 查询序号为 $x$ 的元素上方有几个元素
4. 查询从上往下第 $x$ 个元素的序号
5. 查询从上往下 $x$ 到 $y$ 个元素的 $value$ 的元素和

现在将自顶向下每个元素的 $value$ 值给出，并给出 $m$ 个操作细节，请你给出每个查询操作对应的答案。

Input

第一行输入两个整数 $n, m$， 表示一共有 $n$ 个元素，$m$ 个操作。

第二行输入 $n$ 个整数，依次表示序号为 $1...n$ 的元素的 $value$ 值。

接下来 $m$ 行，每行第一个整数 $opt$ 表示操作类型。

若 $opt = 1$ ，之后两个数 $x, y (x \neq y)$ ，表示将序号为 $x$ 的元素放在序号为 $y$ 的元素前面。

若 $opt =2$ ，之后两个数 $x,y$，表示将序号为 $x$ 的元素对应的 $value$ 值改为 $y$。

若 $opt=3$， 之后一个数 $x$ ，表示询问序号为 $x$ 的元素上方的元素个数。

若 $opt=4$， 之后一个数$x$， 表示查询从上往下第 $x$ 个数的序号。

若 $opt = 5$， 之后两个数 $x,y$， 表示查询从上往下第 $x$ 个数到第 $y$ 个数的 $value$ 的元素和。

Output

对于每一个操作 $3,4,5$ ，输出一行一个整数表示答案。

Samples

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

26
4
1
14
3
26

Constraints

$1 \leq n, m \leq 2 \times 10^5, 0 \leq value_i \leq 10^9$

对于 $opt = 1$ ，有 $1\leq x,y \leq n, \ \ \ x \neq y$

对于 $opt = 2$ ，有 $1\leq x \leq n, \ \ \ 1 \leq y \leq 10 ^ 9$

对于 $opt = 3,4$ ，有 $1\leq x \leq n$

对于 $opt = 5$ ，有 $1\leq x \leq y \leq n$

Resources

2023 UESTC ICPC Training for Data Structures