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]