22157_Sequence

Let S be a sequence of n integers, where S[k] with 1 ≤ k ≤ n denotes the k-th number of S. There is two kinds operation:

1)  move(a, b, c): Move the subsequence S[a]..S[b] to the back of S[c].

    If c equals 0, move the subsequence to the head of S.

2)  sum(a, b): Calculate the sum of S[a]..S[b], output it.

Your task is to write a program, which

• Reads N numbers from the input ( 1 ≤ N ≤ 1,000,000 ).

• Processes M instructions of the input ( 1 ≤ M ≤ 10,000 ). These instructions include moving a subsequence to other place and calculating the sum of a subsequence.

The first line of the input is a single number T, the number of the test cases of the input. Then T blocks each represent a single test case.

The first line of each block contains two integers N and M, representing N numbers and M instruction. The second line contains N 32-bit integers, giving sequence S. Then M lines that is in the following format:

Move  a  b  c    or

Sum  a  b

1 ≤ a ≤ b ≤ N,   0 ≤ c ≤ N,  c < a  or  c > b.

For each Sum operation, output one integer to represent the result, ( i.e. the sum of S[a], S[a+1], ..., S[b] )

2
5
8 2 5 4 2
5
Sum 1 2
Move 2 4 0
Sum 3 4
Move 1 3 4
Sum 2 5
10
8 3 5 7 11 6 1 2 0 9
7
Move 6 7 5
Sum 5 6
Sum 4 4
Move 7 8 0
Move 7 10 0
Sum 1 8
Move 7 9 7

10
12
13
17
7
40