TOPOLAND - To Poland

Little Russell and Mr. Fredricksen are embarking in a new journey with their balloon house. After visiting South America and helping Kevin, the Snipe, they decided to travel to Warsaw, Poland where new specimens of birds might be found.

Their trip is divided into several parts. Due to pressure levels and wind speed, each part of their journey requires that their house is equipped with a minimum number of balloons. As a good boy scout, Russell has already figured out how many balloons are necessary to go through each of the parts. The problem is that atmosphere conditions change and Russel is having trouble determining how many balloons the house should be equipped with to go through continuous parts of the journey, so they don't have to fill up more balloons than necessary.

To help out Russell, you are to develop a program that must deal with the following queries:

  • Russell has added or removed balloons from the house
  • The minimum number of balloons at certain part has changed
  • How many balloons should be added or removed so that the house goes through continuous parts of the journey with the minimum necessary number of balloons?

Input

The first line contains a number T (T ≤ 100), the number of testcases.

Each testcase starts with numbers N (1 ≤ N ≤ 105) and M (0 ≤ M ≤ 103) where N is the number of parts in the journey and M  is the initial number of balloons in the house. Then N numbers follow, one per line, where each number Ni (0 ≤ Ni ≤ 109, 0 ≤ i < N) represents the initial number of balloons necessary to go through part i.

On the next line there is a number Q (1 ≤ Q ≤ 105), the number of queries that you should answer. Each of the next Q lines contains a query in one of the following formats:

  • "A K" -  where A is the actual character 'A' (quotes for clarity) and K (-103K ≤ 103) is the number of balloons that have been added or removed from the house.  It is assured that the total number of balloons in the house is never negative;
  • "B J K" - where B is the actual character 'B' (quotes for clarity), J (0 ≤ J < N) is the number of the part of the journey (0-indexed) and K (0 ≤ K ≤ 109) is the new minimum number of balloons required to go through part J;
  • "C I J" - where C is the actual character 'C' (quotes for clarity), and [I, J], 0 ≤ IJ < N$ is the range that Russell would like to query. For each query of this type, print the difference between the number of balloons currently in the house and the minimum necessary to go through all the parts between I and J inclusive. Note that this query doesn't change the number of balloons in the house.

Output

For each testcase print one line with "Testcase X:" (quotes for clarity) where X is the number of the testcase (0-indexed). For each query of the type "C I J" print one line with the difference between the number of balloons currently in the house and the minimum necessary to go through all the parts between I and J inclusive.

Print one blank line after each testcase.

Example

Input:
2
3 11
5 2 4
1
C 0 2
3 11
16 2 17
5
C 0 2
A -2
C 1 2
B 0 0
C 0 1 Output: Testcase 0:
6

Testcase 1:
6
8
7

Added by:Paulo Costa
Date:2012-01-17
Time limit:0.106s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IME/USP 1 - Brazilian ICPC Training Camp, Jan-Feb/2012

hide comments
2012-11-30 17:20:33 Rafael Giusti
It might be a small detail for almost all programming languages, but where it reads

"Then N numbers follow, one per line, where each number Ni (0 ≤ Ni ≤ 10^9, 0 ≤ i < N) represents the initial number of balloons necessary to go through part i."

According to the sample input, it should read:

"The next line contains a sequence of N numbers N_0, N_1, .., N_{N-1}, where each Ni (0 ≤ N_i ≤ 10^9) represents the initial number of balloons necessary to go through part i."

Last edit: 2012-11-30 17:27:33
2012-11-20 16:26:22 Problem Solver
It's horrible, i have error very early, but judge is checking to 50th test... That's so pointless.

Last edit: 2012-11-20 16:26:37
2012-06-30 15:22:13 Ajey Golsangi
Very large test cases.
2012-03-26 20:45:25 :D
It seems that something changed on SPOJ, at least for new problems. Unlike before, it runs all test cases and only then evaluates. I had errors all the way thought and it still run to 40's.
2012-02-27 19:40:30 :D
TC 0:
You start with 11 balloons and you want to journey the whole way. That requires 5 balloons (the max): |5-11|=6.

TC 1:
Again 11 bl. at start. First query again for all parts, so the max is 17: |17-11|=6.
Then we are taking away 2 bl. so we have 9. And asking for the range <1;2> so max{2,17}: |17-9|=8.
We change requirement for bl. on first part to 0. The new sequence is (0,2,17). And finally query for range <0,1>, max{0,2}: |2-9|=7.
2012-02-07 11:15:24 Nnavneetsinha
please help me out .please explain me the test cases .
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.