Background

Yesterday, Little H saw the problem luogu 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.

Problem Description

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.

Input Format

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.

Output Format

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

5 10
57770 55352 18768 21847 79100 
M 1 4
M 3 2
Q 5 2
M 3 4
M 3 5
M 4 4
M 3 1
D 1
Q 2 2
Q 2 1

-1
55352
113122

30 100
2193 75245 24438 95450 96514 84854 15292 9488 37488 940 52991 15190 64052 17398 80379 77861 88717 34751 16783 88345 27612 21748 79776 43058 35590 49064 45012 37206 70870 30643 
M 18 26
M 28 27
M 25 4
M 12 22
M 26 15
M 3 1
M 20 20
M 7 21
M 18 29
M 21 26
M 29 10
M 27 23
M 30 28
M 22 10
M 13 21
M 1 23
M 25 9
M 29 27
M 23 25
M 11 12
M 1 4
M 26 14
M 26 9
D 4
M 16 8
M 16 20
M 4 27
M 9 20
M 11 1
M 19 8
Q 12 7
M 5 10
D 20
Q 29 2
Q 9 15
M 29 21
D 5
M 23 8
M 6 6
D 23
D 6
Q 4 8
D 21
Q 29 23
Q 19 4
M 21 21
M 20 25
M 27 29
D 2
Q 7 2
M 7 15
Q 11 18
D 26
Q 21 18
M 22 11
M 12 12
M 20 15
M 22 4
D 20
M 4 5
M 12 2
Q 27 20
M 30 2
M 28 9
M 20 11
M 10 21
M 12 24
Q 14 14
M 6 29
Q 13 18
Q 10 3
Q 23 3
D 4
M 27 13
M 6 23
M 7 14
Q 12 17
M 18 25
Q 2 19
D 3
D 9
Q 2 16
Q 3 8
Q 4 10
D 24
M 21 4
Q 17 15
Q 19 7
Q 1 24
Q 9 18
D 12
M 4 16
M 27 21
D 26
M 5 14
M 15 19
M 21 26
M 18 27
Q 21 8
Q 18 13

52230
-1
-1
254468
291078
112233
-1
231636
62363
-1
17398
178645
25378
219268
-1
419122
347453
-1
-1
-1
274542
-1
269126
-1
178645

Hint

(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