Description

八云蓝自动机维护了一个长度为 $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}$$

Input Format

• 第一行两个整数 $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$，描述一次询问，具体执行方式如题面所示。

Output Format

• 共 $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

Hint

• 本题有且仅有一个 $\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$。