Sequence Operations Query

You are given n sequences, where initially each sequence consists of a single element. The i-th sequence contains one element with value a_i. Then you will be given m operations. There are three types of operations:

1. M x y: Merge the entire sequence containing element x by appending it at the end of the sequence containing element y. If x and y are already in the same sequence, do nothing.
2. D x: In the sequence that contains element x, break the sequence at element x (i.e. remove x and all elements after it) and form a new sequence with these elements.
3. Q x y: If elements x and y are in the same sequence, output the sum of all elements between x and y (inclusive), otherwise output -1. In a query, the order of x and y does not matter; you should sum from the element that appears first to the one that appears later.

Input Format: The first line contains two integers n and m. The second line contains n integers a₁, a₂, ..., a_n representing the initial values. Each of the next m lines contains an operation in one of the three formats described above.

Output Format: For each query operation, output the corresponding result on a new line.

Note: All formulas are expressed in LaTeX format when applicable.

inputFormat

The input begins with a line containing two integers n and m. The next line contains n integers a1, a2, ..., an. Each of the following m lines describes an operation in one of the following forms:

M x y D x Q x y

outputFormat

For each operation of type Q, output the required sum if the two specified elements are in the same sequence, or -1 if they are not.

sample

5 7
1 2 3 4 5
Q 1 1
M 1 2
Q 1 2
D 1
Q 1 2
M 1 4
Q 1 4

1
3
-1
5