P4847 Galaxy Heroes Legend V2

Yesterday, Little H saw the problem [luogu P1196](https://www.luogu.com.cn/problem/P1196), which triggered his feelings about heroes (fog). However, he could not solve it, so he went to ask Little W for help. After explaining that problem, Little W had a sudden idea—why not modify this problem a bit? So, a very easy “check-in” problem appeared.

Some dalao said: Make the statement simpler so I can get an AC in one minute! So Little W had to simplify the meaning: Given $n$ sequences of length $1$, the $i$-th sequence contains one element with value $a_i$. Then there are three types of operations: 1. `M x y`: move the sequence containing $x$ to after the sequence containing $y$. If $x$ and $y$ are already in the same sequence, do nothing. 2. `D x`: cut the sequence containing $x$ at position $x$. That is, take $x$ and all elements after $x$ out as a new sequence. 3. `Q x y`: query the sum of values of all elements between $x$ and $y$ (including $x$ and $y$). If $x$ and $y$ are not in the same sequence, output `-1`.

The first line contains two integers $n,m$, representing the number of elements and the number of operations. The second line contains $n$ integers, which are $a_i$. The next $m$ lines each describe one operation, in one of the following forms: `M x y`, `D x`, or `Q x y`, corresponding to the description.

For each `Q x y`, output one integer, the sum of the values of all elements in the queried range.

(The problem setter kindly provided a larger sample!) **[Sample $1$ Explanation]** At the beginning there are $5$ sequences (each row is one sequence), arranged as: ``` 1 2 3 4 5 ``` The first operation puts $1$ after $4$, becoming: ``` 2 3 4,1 5 ``` The second operation puts $3$ after $2$, becoming: ``` 2,3 4,1 5 ``` Then query the sum between the $5$-th element and the $2$-nd element. Since it does not exist, output `-1`. Append the sequence containing $3$ after the sequence containing $4$, becoming: ``` 4,1,2,3 5 ``` Next it becomes $5,4,1,2,3$, i.e. all elements are in $1$ sequence, so the next two merge operations are useless. Then delete the numbers after $1$, becoming: ``` 1,2,3 5,4 ``` Query $2$ to $2$, output $a_2$, which is $55352$. Query $2$ to $1$, output $a_2+a_1$, which is $113122$. **[Constraints]**  ~~To avoid some messy tricks (maybe it cannot be avoided anyway)~~, **the first $5$ points are scored in the traditional way, $10$ points per test point; the last five points are bundled as a subtask: you must pass all of them to get $50$ points, otherwise you get $0$ points.** For all testdata, $1 \le x,y \le n$, $1 \le a_i \le 10^9$. Translated by ChatGPT 5