#216760. [GKS 2020 #C] Candies

Carl has an array of candies. The i-th element of the array (indexed starting from 1) is , representing sweetness value of the i-th candy. He would like to perform a series of operations. There are two types of operation:

• Update the sweetness value of a candy in the array.
• Query the sweetness score of a subarray.

The sweetness score of a subarray from index to is:

More formally, the sweetness score is the sum of , for all from to inclusive.

For example, the sweetness score of:

• is
• is
• is

Carl is interested in finding out the total sum of sweetness scores of all queries. If there is no query operation, the sum is considered to be 0. Can you help Carl find the sum?

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing and . The second line contains integers describing the array. The i-th integer is . The j-th of the following lines describe the j-th operation. Each line begins with a single character describing the type of operation ( for update, for query).

• For an update operation, two integers and follow, indicating that the -th element of the array is changed to .
• For a query operation, two integers and follow, querying the sweetness score of the subarray from the -th element to the -th element (inclusive).

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the total sum of sweetness scores of all the queries.

样例输入 1

2
5 4
1 3 9 8 2
Q 2 4
Q 5 5
U 2 10
Q 1 2
3 3
4 5 5
U 1 2
U 1 7
Q 1 2

样例输出 1

Case #1: -8
Case #2: -3

In sample case #1:

• The first query asks for the sweetness score of [] which is .
• The second query asks for the sweetness score of [] which is .
• The third query asks for the sweetness score of [] which is .

Thus, the final output should be .

In sample case #2:

• The first and only query asks for the sweetness score of [] which is .

Thus, the final output should be -3.

Limits

.

, for all .

and for at most test cases.

For the remaining cases, and .

If the j-th operation is an update operation, and .

If the j-th operation is a query operation, .

Test Set 1

There will be at most update operations.

Test Set 2

There are no special constraints.