You are given a sequence of N integers A₁, A₂ ... A_N. (-10000 <= A_i <= 10000, N <= 50000)

Let S_i denote the sum of A₁ ... A_i. You need to apply M (M <= 50000) operations:

• 0 x y k: increase all integers from A_x to A_y by k (1 <= x <= y <= N, -10000 <= k <= 10000).
• 1 x y: ask for max{ S_i | 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 :)