题目背景

注意：本题题意和 八云蓝自动机Ⅱ 并不一致，请仔细阅读。

作为八云紫的式神，八云蓝有着不同于其他一般式神的强大的计算能力。也就是说，八云蓝可以用自己的心算能力模拟出一台在现世中的确定性状态自动机。

而这，就是传说中的

$$\textbf{\textsf{「八云蓝自动机」}}$$

当然，尽管八云蓝的计算能力可以用于模拟一台计算机的操作，但是由于其中并没有设定任何的程序，于是可以实现的功能只能通过学习得到。而作为幻想乡的闲者，八云紫教会了蓝有关于数组的知识。一个数组由若干个存储单元组成，每个单元都可以存储一个整数。

而为了检测这种「八云蓝自动机」的可靠性，紫准备了一条非常简单的模拟题，用于测试蓝的心算能力。

然而，尽管蓝可以很快（ $<10^{-9961}s$ ）得出结果，但是八云紫实在是懒得去构造标准答案了。因此，你被钦定计算出这条题目的答案。

题目描述

八云蓝自动机维护了一个长度为 $n$ 的序列 $A$ ，每个元素都有一个初始值。同时自动机会支持以下三种操作：

• $\colorbox{f0f0f0}{\verb!1 x k!}$ ：将 $A_x$ 的值修改为 $k$。

• $\colorbox{f0f0f0}{\verb!2 x y!}$ ：交换 $A_x$ 与 $A_y$ 的值。

• $\colorbox{f0f0f0}{\verb!3 x!}$ ：查询 $A_x$ 的值。

为了测试八云蓝自动机的效率，紫需要进行非常非常多次的测试。为了生成每个测试的所有操作，紫构造出了一个长度为 $m$ 的操作序列 $B$ ， $B$ 中的元素就是八云蓝自动机可以执行的一个操作。

紫会向蓝发起一共 $q$ 次测试。每次测试，紫会给出一个二元组 $(l,r)$ ，含义是让八云蓝自动机依次执行 $B_l,B_{l+1},\cdots B_r$ 这一共 $(r-l+1)$ 个操作。当然，紫不希望自动机的输出会太长，于是对于每次测试，你只要告诉她这些操作中所有操作 $3$ 的结果之和即可。注意：任意两次测试并不会互相干扰，每次操作结束后数列 $A$ 会回到初始状态。

此外，紫不希望用非常非常大的数字刁难你，于是答案对 $2^{32}$ 取模就行了（即 $\text{unsigned int}$ 自然溢出）。

输入格式

• 第一行两个整数 $n,m$ ，含义如题面所示。

• 第二行 $n$ 个整数，表示序列 $A$ 的初始值。

• 接下来 $m$ 行，描述操作序列 $B$ 。对于每个操作，首先是一个整数 $op$ 描述操作的种类。

  • 如果 $op = 1$，接下来两个整数 $x,k$ ，描述一个操作 $1$ 。

  • 如果 $op = 2$，接下来两个整数 $x,y$ ，描述一个操作 $2$ 。

  • 如果 $op = 3$，接下来一个整数 $x$ ，描述一个操作 $3$ 。

• 接下来一行，一个整数 $q$，表示八云紫发起的测试总数。

• 接下来 $q$ 行，每行有两个整数 $l,r$，描述一次测试，具体的执行方式如题面所示。

输出格式

• 共 $q$ 行，每行一个整数，表示此次测试的结果。

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

14
11
10
17
10
8
0
8
15
4

提示

数据范围及约定

$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,m,q} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & 1\le n,m,q\le 10^3 & \text{无} & 10 \cr\hline 2 & \text{无特殊限制} & \text{无操作 1} & 20\cr\hline 3 & \text{无特殊限制} & \text{无操作 2} & 20\cr\hline 4 & \text{无特殊限制} & \text{操作 3 次数}\le 10 & 20 \cr\hline 5 & \text{无特殊限制}& \text{无}& 30 \cr\hline \end{array}$$

• 对于 $100\%$ 的数据，满足：

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

  • $1 \le a_i,k \le 10^9;1 \le op \le 3;1 \le x,y \le n;x \neq y $ 。

  • $1 \le l \le r \le m$ 。