P7708 "Wdsr-2.7" Yakumo Ran Automaton I

**Note: The meaning of this problem is not the same as Yakumo Ran Automaton II. Please read carefully.** As Yakumo Yukari's shikigami, Yakumo Ran has powerful computing ability that is different from ordinary shikigami. In other words, Yakumo Ran can use mental calculation to simulate a deterministic finite automaton in the real world. And this is the legendary $$\textbf{\textsf{「Yakumo Ran Automaton」}}$$ Of course, although Yakumo Ran's computing ability can be used to simulate the operations of a computer, since no program is set inside it, the functions it can achieve can only be learned. As a leisurely youkai in Gensokyo, Yakumo Yukari taught Ran knowledge about arrays. An array is made of several storage cells, and each cell 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 ( $

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}$).

- 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 $q$ lines. Each line contains one integer, representing the result of that test.

#### 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