银河英雄传说V2

题目背景

小H昨天看到了luogu P1196这一题,触发了他内心中对英雄的感慨/雾。可是无奈他不会这一题,只好去请教小W。在讲完那一题之后,小W灵机一动——不如改一下这道题吧。 于是,一个很水的签到题出现了。

题目描述

某dalao:把题目说简单一点,方便让我一分钟A掉! 于是小W只好把题意简化一下: 给定n个长度为1的序列,第i个序列中有一个元素,值为ai,接下来有三种操作: 1. `M x y`,表示把x所在的序列放到y所在的序列之后。如果x,y已经在同一个序列,则不进行操作。 2. `D x`,表示把x所在的序列中从x处断开,也就是把x及x之后的元素单独取出来作为一个序列。 3. `Q x y`,表示查询x到y之间(包括x和y)所有元素的值之和。如果x和y不在同一个序列之中,输出-1.

输入输出格式

输入格式


第一行为两个数n,m,分别代表元素个数和操作次数。第二行有n个数,为ai。 接下来m行,每行包括三种情况:M x y,D x或Q x y,与题目描述对应。

输出格式


对于每一个Q x y,输出一个数,表示所有元素的值之和。

输入输出样例

输入样例 #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

输出样例 #1

-1
55352
113122

输入样例 #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

输出样例 #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

说明

(出题人非常良心地给了一个大一点的样例!) 样例1解释: 首先有5个序列(一个横排为一个序列),排列如下: ``` 1 2 3 4 5 ``` 第一个操作将1放到4的后面,变成 ``` 2 3 4,1 5 ``` 第二个操作将3放到2后面,变成 ``` 2,3 4,1 5 ```` 然后查询第5个元素到第2个元素之间的和,由于不存在,输出-1; 将3所在的序列加到4所在的序列后面,变成 ``` 4,1,2,3 5 ``` 接下来变成了5,4,1,2,3,也就是所有元素都在1个序列了,因此接下来的两个合 并操作没有用了,然后把1之后的数字删除,变成: ``` 1,2,3 5,4 ``` 查询2到2,输出2的值,也就是55352; 查询2到1,输出2+1的值,也就是113122. ![Luogu](https://cdn.luogu.com.cn/upload/pic/30577.png) ~~为了避免某些乱搞(可能避免不了)~~,**前5个点按照传统方式计分,每个测试点10分;后五个点为subtask,必须全部通过才能得分,否则不得分。** 对于所有数据,1<=x,y<=n,1<=ai<=10^9