题目背景

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

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

而这，就是传说中的

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

由于八云蓝自动机通过心算的方式进行运算，因此她还支持一项特异功能，就是一次对一整块数据进行操作。这加强了八云蓝自动机的优越性。

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

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

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

题目描述

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

• $\colorbox{f0f0f0}{\verb!1 l r k!}$ ：将区间 $[l,r]$ 内的所有数字全都变为 $k$ ，即 $A_l\gets k,A_{l+1}\gets k,\cdots ,A_r\gets k$ 。

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

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

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

设 $\Upsilon(l,r)$ 表示从初始状态开始，依次执行 $B_l,B_{l+1},\cdots B_r$ 操作后，所有操作 $3$ 的结果之和。特别地，如果这些操作中没有操作 $3$ ，那么 $\Upsilon(l,r)=0$ 。

紫会向八云蓝自动机发起 $q$ 次询问，每次给出一组 $(l,r,p)$ ，八云蓝自动机需要计算出

$$\left(\sum_{i=l}^r \Upsilon(i,p)\right) \mod 2^{32} $$

输入格式

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

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

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

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

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

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

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

• 接下来 $q$ 行，每行有三个整数 $l,r,p$，描述一次询问，具体执行方式如题面所示。

输出格式

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

10 10
12 11 6 6 1 18 9 1 13 20 
2 1 8
1 7 7 12
2 4 10
2 5 10
2 9 5
3 7
1 4 8 7
1 1 9 13
3 5
3 6
10
1 4 10
3 3 3
2 2 7
1 4 6
2 2 9
1 8 8
2 6 8
2 6 8
2 5 6
1 4 9

146
0
12
42
25
60
48
48
39
94

提示

• 本题有且仅有一个 $\textbf{Subtask}$ 。在本 $\text{Subtask}$ 中，前几组数据满足 $n,m,q \le 5 \times 10^3$，可供检验你的算法的正确性。

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

  • $1 \le n,m,q \le 3 \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 n$；对于所有查询 $1 \le l \le r \le p \le m$。