Description

$A$国在海岸线沿直线布置了$N$ 个工兵营地。$C$国通过先进的监测手段对$A$国每个工兵营地的人数都掌握得一清二楚。每个工兵营地的人数都可能发生变动，可能增加或减少若干人手。

Input

第$1$行包含一个整数$T$ ，表示有$T$ 组数据。每组数据的第$1$行都包含一个正整数$N （N ≤50000）$，表示有$N$ 个工兵营地。接下来有$N$ 个正整数，第$i$ 个正整数$a_i$ 代表第i 个工兵营地开始时有$a_i$ 个人$（1≤a_i ≤50）$。再接下来每行都有一条命令，每组数据最多有$40000$条命令，命令有$4$种形式：$①Add i j ，$表示第$i$ 个营地增加$j$ 个人$（j≤30）；②Sub i j$，表示第$i$ 个营地减少$j$ 个人$（j ≤30）；③Query i j ，i ≤j ，$表示查询第$i ～j$ 个营地的总人数（$int$以内）；④$End$，表示结束，在每组数据的最后出现。命令中的$i$ 和$j$ 均为正整数。

Output

对第$i$ 组数据，首先单行输出$“Case i:”$，然后对每个$Query$都单行输出查询区间的总人数。

Samples

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

Case 1:
6
33
59

来源

HDU1166