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.

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.