Background

Note: The meaning of this problem is not the same as Yakumo Ran Automaton I. Please read carefully.

As Yakumo Yukari’s shikigami, Yakumo Ran has powerful computing ability unlike ordinary shikigami. That is, Yakumo Ran can use mental calculation to simulate a deterministic finite automaton in the real world. Through the previous practice, the Yakumo Ran Automaton has become even stronger.

And this is the legendary

$$\textbf{\textsf{「Yakumo Ran Automaton$^{\text{plus}}$」}}$$

Since the Yakumo Ran Automaton operates by mental calculation, it also supports a special ability: performing an operation on an entire block of data at once. This further improves the advantage of the Yakumo Ran Automaton.

Of course, although Ran’s computing ability can be used to simulate computer operations, since no program is set inside it, the functions it can achieve can only be obtained through learning. As a闲者 (xianzhe) of Gensokyo, Yakumo Yukari taught Ran knowledge about arrays. An array consists of several storage units, and each unit can store an integer.

To test the reliability of this 「Yakumo Ran Automaton」, Yukari prepared a very simple simulation problem to test Ran’s mental calculation ability.

However, although Ran can quickly ( $<10^{-10^{9961}}s$ ) get the result, Yakumo Yukari is too lazy to construct the standard answer. Therefore, you are chosen to compute the answer for this problem.

Problem Description

The Yakumo Ran Automaton maintains a sequence $A$ of length $n$, where each element has an initial value. The automaton supports the following three operations:

• $\colorbox{f0f0f0}{\verb!1 l r k!}$: Set all numbers in the range $[l,r]$ to $k$, i.e., $A_l\gets k,A_{l+1}\gets k,\cdots ,A_r\gets k$.

• $\colorbox{f0f0f0}{\verb!2 x y!}$: Swap the values of $A_x$ and $A_y$.

• $\colorbox{f0f0f0}{\verb!3 x!}$: Query the value of $A_x$.

To test the efficiency of the Yakumo Ran Automaton, Yukari needs to run a huge number of tests. To generate all operations for each test, Yukari constructed an operation sequence $B$ of length $m$, where each element of $B$ is an operation that the Yakumo Ran Automaton can execute.

Let $\Upsilon(l,r)$ denote the sum of the results of all type $3$ operations after starting from the initial state and executing operations $B_l,B_{l+1},\cdots B_r$ in order. In particular, if there is no type $3$ operation among them, then $\Upsilon(l,r)=0$.

Yukari will ask the Yakumo Ran Automaton $q$ queries. Each query gives a triple $(l,r,p)$, and the automaton needs to compute

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

Input Format

• The first line contains two integers $n,m$, with meanings as described above.

• The second line contains $n$ integers, the initial values of sequence $A$.

• The next $m$ lines describe the operation sequence $B$. For each operation, the first integer is $op$, indicating the operation type.

  • If $op = 1$, then three integers $l,r,k$ follow, describing a type $1$ operation.

  • If $op = 2$, then two integers $x,y$ follow, describing a type $2$ operation.

  • If $op = 3$, then one integer $x$ follows, describing a type $3$ operation.

• The next line contains an integer $q$, the total number of queries initiated by Yakumo Yukari.

• The next $q$ lines each contain three integers $l,r,p$, describing a query, with the execution as stated above.

Output Format

• Output $q$ lines. Each line contains one integer, the answer to the corresponding query.

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

• This problem has one and only one $\textbf{Subtask}$. In this $\text{Subtask}$, the first few testdata satisfy $n,m,q \le 5 \times 10^3$, which can be used to check the correctness of your algorithm.

• For $100\%$ of the testdata, it holds that:

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

  • For all operations, $1 \le l \le r \le n$; for all queries, $1 \le l \le r \le p \le m$.

Translated by ChatGPT 5