Background

After seeing problem luogu P1196 yesterday, Little H was inspired by the heroes in his heart. However, he couldn't solve the problem and had to consult Little W. After explaining the problem, Little W had an idea—why not modify the problem?

Thus, a straightforward problem emerged.

Problem Description

A dalao: Simplify the problem so I can solve it in a minute!

So, Little W simplified the problem:

Given n sequences of length 1, each containing one element with value ai. There are three types of operations:

1. M x y, which means to append the sequence containing x to the end of the sequence containing y. If x and y are already in the same sequence, no operation is performed.
2. D x, which means to split the sequence containing x at x, making x and all elements after it a separate sequence.
3. Q x y, which means to query the sum 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 numbers n and m, representing the number of elements and the number of operations, respectively. The second line contains n numbers, which are the values ai.

The next m lines each contain one of the following: M x y, D x, or Q x y, corresponding to the operations described.

Output Format

For each Q x y operation, output a single number representing the sum of all elements between x and y.

Sample Input and Output

Sample Input #1

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

Sample Output #1

-1
55352
113122

Sample Input #2

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

Sample Output #2

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

Notes

(The problem setter kindly provided a larger sample!)

Sample 1 Explanation:

Initially, there are 5 sequences (each row represents a sequence):

1
2
3
4
5

The first operation appends sequence 1 to the end of sequence 4, resulting in:

2
3
4,1
5

The second operation appends sequence 3 to the end of sequence 2, resulting in:

2,3
4,1
5

Then, a query for the sum between element 5 and element 2 is made, which does not exist, so -1 is output.

Appending sequence 3 to the end of sequence 4 results in:

4,1,2,3
5

Subsequently, all elements are in one sequence, so the next two merge operations are redundant. Splitting the sequence at element 1 results in:

1,2,3
5,4

A query for the sum between element 2 and element 2 outputs the value of element 2, which is 55352.

A query for the sum between element 2 and element 1 outputs the sum of elements 2 and 1, which is 113122.

For all data, 1 ≤ x, y ≤ n, 1 ≤ ai ≤ 10^9.

The first 5 points are scored traditionally, with each test case worth 10 points. The last 5 points are a subtask, where all must be passed to score, otherwise no points are awarded.

见题面 Input 部分

见题面 Output 部分