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 x k!}$: Modify $A_x$ to $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 one operation that the automaton can execute.

Yukari will conduct a total of $q$ tests. In each test, Yukari gives a pair $(l, r)$, meaning that the automaton should execute in order the $(r - l + 1)$ operations $B_l, B_{l+1}, \cdots, B_r$. Of course, Yukari does not want the output to be too long, so for each test, you only need to tell her the sum of the results of all operation $3$ within these operations. Note: any two tests do not affect each other. After each test, the sequence $A$ will return to its initial state.

Also, Yukari does not want to trouble you with extremely large numbers, so you only need to take the answer modulo $2^{32}$ (i.e., natural overflow of $\text{unsigned int}$).

Input Format

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

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

• The next $m$ lines describe the operation sequence $B$. For each operation, an integer $op$ comes first to describe the type of the operation.

  • If $op = 1$, the next two integers are $x, k$, describing an operation $1$.

  • If $op = 2$, the next two integers are $x, y$, describing an operation $2$.

  • If $op = 3$, the next integer is $x$, describing an operation $3$.

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

• The next $q$ lines each contain two integers $l, r$, describing one test. The execution method is as stated above.

Output Format

• Output $q$ lines. Each line contains one integer, representing the result of that test.

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

Hint

Constraints and Notes

$$\def\arraystretch {1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,m,q} & \textbf{Special Property} & \textbf{Score}\cr\hline 1 & 1\le n,m,q\le 10^3 & \text{None} & 10 \cr\hline 2 & \text{No special limits} & \text{No operation 1} & 20\cr\hline 3 & \text{No special limits} & \text{No operation 2} & 20\cr\hline 4 & \text{No special limits} & \text{Number of operation 3}\le 10 & 20 \cr\hline 5 & \text{No special limits}& \text{None}& 30 \cr\hline \end{array}$$

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

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

Translated by ChatGPT 5