UNTITLE1 - Untitled Problem II

no tags 

You are given a sequence of N integers A1, A2 ... AN. (-10000 <= Ai <= 10000, N <= 50000)

Let Si denote the sum of A1 ... Ai. You need to apply M (M <= 50000) operations:

  • 0 x y k: increase all integers from Ax to Ay by k (1 <= x <= y <= N, -10000 <= k <= 10000).
  • 1 x y: ask for max{ Si | x <= i <= y }.(1 <= x <= y <= N)

Input

  • In the first line there is an integer N.
  • The following line contains N integers that represent the sequence.
  • The third line contains an integer M denotes the number of operations.
  • In the next M lines, each line contains an operation "0 x y k" or "1 x y".

Output

For each "1 x y" operation, print one integer representing its result.

Example

Input:
5
238 -9622 5181 202 -6943
5
1 3 4
0 5 5 4846
1 3 5
0 3 5 -7471
1 3 3

Output:
-4001
-4001
-11674

Use signed 64-bit integer :)


hide comments
[Rampage] Blue.Mary: 2010-02-04 09:43:31

A little constant optimization is needed.

Last edit: 2010-02-04 09:43:49
Matt Garman: 2009-09-02 21:09:05

Are the operations cumulative? Or is the sequence "reset" back to original after ever "1 x y" operation?

Ivan Katanic: 2009-08-20 17:22:23

Increase an consecutive interval[x,y].

piyifan: 2009-06-29 01:41:45

what does increase all integers from Ax to Ay by k mean?Incease an consecutive interval[x,y] or increase all integer big than Ax and less than Ay.


Added by:Qu Jun
Date:2008-08-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Not an own problem