Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Fafa and Array

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFafa 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.

Input

The first line contains one integer *n* (3 ≤ *n* ≤ 10^{5}) — the length of the array.

The second line contains *n* positive integers *a*_{1}, *a*_{2}, ..., *a*_{n} (0 < *a*_{i} ≤ 10^{9}) — the array elements.

The third line contains an integer *q* (1 ≤ *q* ≤ 10^{5}) — the number of queries.

Then *q* lines follow, line *i* describes the *i*-th query and contains four integers *t*_{i} *l*_{i} *r*_{i} *x*_{i} .

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.

Examples

Input

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

Output

2

8

Input

5

1 2 3 4 5

4

1 2 4 2

2 2 4 1

2 3 4 1

1 2 4 2

Output

6

10

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2018 15:23:43 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|