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

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