Fafa and Array
Description
Fafa has an array A of n positive integers, the function f(A) is defined as 
. He wants to do q queries of two types:
- 1 l r x — find the maximum possible value of f(A), if x is to be added to one element in the range [l, r]. You can choose to which element to add x.
- 2 l r x — increase all the elements in the range [l, r] by value x.
Note that queries of type 1 don't affect the array elements.
The first line contains one integer n (3 ≤ n ≤ 105) — the length of the array.
The second line contains n positive integers a1, a2, ..., an (0 < ai ≤ 109) — the array elements.
The third line contains an integer q (1 ≤ q ≤ 105) — the number of queries.
Then q lines follow, line i describes the i-th query and contains four integers ti li ri xi 
.
It is guaranteed that at least one of the queries is of type 1.
For each query of type 1, print the answer to the query.
Input
The first line contains one integer n (3 ≤ n ≤ 105) — the length of the array.
The second line contains n positive integers a1, a2, ..., an (0 < ai ≤ 109) — the array elements.
The third line contains an integer q (1 ≤ q ≤ 105) — the number of queries.
Then q lines follow, line i describes the i-th query and contains four integers ti li ri xi .
It is guaranteed that at least one of the queries is of type 1.
Output
For each query of type 1, print the answer to the query.
Samples
5
1 1 1 1 1
5
1 2 4 1
2 2 3 1
2 4 4 2
2 3 4 1
1 3 3 2
2
8
5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2
6
10