SIGNGAME - Red Balls

After the previous game ,each ball is either red or green in color. Dope tells you that he is changing the color of all balls in the range i to j (both inclusive),that is red balls to green and green balls to red. And then he asks you to tell the total extra mass of red balls over green balls for some range between i to j (inclusively). As you like red balls, you will try to maximize the total mass of red balls mass over the green balls. So He allows you to choose any range inside the range i, j inclusively which gives the maximum extra mass of red balls over the green balls. When you choose a range, you have to take all the green and red balls that belong to the range.

Convention:
(+) positive mass represents red ball mass
(-) negative mass represents green ball mass

Input

T number of test cases
next T test cases follow each contains:
N number of balls
next line contains N mass of ball (positive or negative)
next line Q number of operation and query next Q lines contain
c a b
c = 0 change the color of balls in range a, b inclusively
c = 1 print the maximum extra mass of red balls over green in the range a, b inclusively.

Output

each line for print query

limit:
1 <= T < 10
1 <= N < 100000
1 <= Q < 100000
0 <= a <= b < N
c = 0 or 1
abs(individual mass)<1000

Example

Input:
1
5
2 -3 4 5 -2
4
0 0 2
1 0 2
1 1 3
0 1 1

Output:
3
5

[you have to choose a range, if all balls are green in the range you have to print (-)ve answer]


Added by:pankaj
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own, DOPE 2011

hide comments
2011-02-21 17:54:54 Siarhei Kulik
What are the restrictions for the mass of balls?

you have to choose a range however you don't find any red balls.


Last edit: 2022-12-11 23:07:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.