Captain Huang's secret background

Captain Huang is an active thinker and good at geometry, math.But the most amazing characteristic of Captain Huang is her secret background .Due to the seriousness and secrecy of her background,we have to define a query to explain it.

Given integer sequence a₁,a₂,...,a_n, you can choose a pair of integers (x,y) (1<=x<=y<=n),such that the sum of a_x+a_x+1+..+a_y is positive and as large as possible.The subsegment a_x, a_x+1, .., a_y is called positive maximum subsegment(PMS) of sequence a₁,a₂,...,a_n.

Now,we define a CRH query. In reply to it you should reverse  a PMS (x,y) of sequence a₁,a₂,...,a_n (i.e. a[i]=-a[i],(x<=i<=y)) and print the sum of PMS of the modified sequence a₁,a₂,...,a_n which is called CRH and should be as large as possible.

You should run instructions of three types：
"0 i val" means performing a_i=val
"1 l r" means performing a_i=-a_i for all a_i such that l<=i<=b

"2 l r" means querying CRH of a_l,a_l+1,..,a_r. If you can not find PMS or CRH ,just print "0". Note that the reversing operation in querying CRH will not affect the original sequence.

Hint(you can read it after solving the problem because it is irrelevant to the problem):

If you succeed in solving the problem ,Congratulations! I suggested that you can have a try on the following problem after the contest. Because the similarity of solution code of the two problem are up to 99%.
The query of the challenging problem is that you should choose at most k pairs of integers (x1,y1),(x2,y2),...,(xt,yt) (l≤x1≤y1< x2 ≤ y2 < ... < xt ≤ yt ≤ r; t ≤ k)such that a_x1+a_x1+1+...+a_y1+a_x2+a_x2+1+...+a_y2.+...+a_xt+a_xt+1+...+a_yt is as large as possible.Note you can choose 0 subsegments whose sum is 0.
There is a interesting proof of the problem based on flow!

The first line contains integer n (1≤n≤1e5), showing how many numbers the sequence has. The next line contains n integers a₁,a₂,...,a_n (|ai|≤500).

The third line contains integer m (1≤m≤1e5) — the number of instructions. The next m lines contain the instructions in the format, given in the statement.

All changing queries fit into limits: 1≤i≤n, |val|≤500.

For each query to count CRH print the reply . Print the answers to the queries in the order, in which the queries follow the input.

15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
8
2 6 12
0 6 5
0 10 -7
1 4 9
1 7 9
0 10 -3
2 4 10
2 1 15

4
0
11

In the first query of the first example the first PMS pair is(11,12) and after reversing the second PMS pair is (6,6). So the CRH will be 4. In the second query of the first example the first PMS pair is(4,4) and after reversing the second PMS pair is none. So the CRH will be 0. In the third query of the first example the first PMS pair is(2,4) and after reversing the second PMS pair is (11,12). So the CRH will be 11.

Compiler C C++ Java Python2 Python3

Use advanced editor

Code