种西瓜

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

现在郭小冉决定在瓜场种m年西瓜。
首先她有n块西瓜地。
第i块西瓜地每年可以将会生产出b(i)颗西瓜。
每一年ta都会回到西瓜地。
每一年ta有两种操作,一种是选择一段连续的土地查询它们这些年的产量总和。
另外一种是选择一段连续的土地,并把它们的每一块的年产量都增加1.

Input

每组输入包含多组测试数据
对于每组测试数据
第一行包含西瓜地的块数n。
第二行包含n块西瓜地的年产量。
第三行包含m 代表接下来的年数。
每一年都会有一个操作
查询格式如下:
查询产量 Q s t (1<=s,t<=n)
增加年产量 I s t (1<=s,t<=n)
只有在查询的时候进行输出。

1<=n<=100000

1<=m<=100000

1<=b(i)<=100000

Output

对于每组测试,输出一行由空格隔开的整数(个数为输入中查询Q的个数)

Sample Input

4
1 1 1 1
3
Q 1 3
Q 1 4
Q 2 4
4
1 2 3 4 
3
Q 1 4
I 1 3
Q 2 4

Sample Output

3 8 9
10 29

Hint

Source

2018年西安邀请赛K题