Time Limit: 2.0 s

Memory Limit: 512.0 MB

Description

You are given an integer arry of size \(N\). and \(Q\) queries in the following format :
\(1 L R X\) : add X to all index from \(L\) to \(R\) inclusive
\(2 L R\) : print the maximum value in range \(L\) to \(R\) inclusive

Input

first line takes an integer \(T\) : number of testcases
first line of each testcase takes an integer \(N\) : size of the array
second line takes \(N\) integers: elements of the array
third line takes an integer \(Q\) : number of queries
each of the next \(Q\) lines takes a query

\(1 <= T <= 1000\)
\(1 <= N,Q <= 10^5\)
\(0 <= A_i <= 10^9\)
\(1 <= L <= R <= N\)
\(-10^9 <= X <= 10^9\)

Output

for each of type 2 query print the result in a new line.

Sample

1
5
3 1 2 4 5
5
2 1 3
1 2 4 2
2 1 3
1 3 5 -6
2 1 3

3
4
3