Skyline Queries

This problem involves maintaining and updating the skyline of a row of buildings. Each building has an initial height. You will receive a series of queries that either update the heights of a consecutive segment of buildings or ask for the maximum height within a given segment.

There are two types of queries:

• Update Query: Given in the form \(1\ l\ r\ h\), increase the height of every building in the range \(l\) to \(r\) (inclusive, 0-indexed) by \(h\). Formally, for every \(i\) where \(l \le i \le r\), update \(h_i := h_i + h\).
• Maximum Query: Given in the form \(0\ l\ r\), determine the maximum height among the buildings in the range \(l\) to \(r\) (inclusive, 0-indexed). That is, compute \(\max_{i=l}^{r} h_i\).

You are required to process the queries in the order they are given and print the result of each maximum query on a new line.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (T), representing the number of test cases. Each test case has the following structure:

1. The first line contains an integer (N), denoting the number of buildings.
2. The second line contains (N) space-separated integers representing the initial heights of the buildings.
3. The third line contains an integer (Q), denoting the number of queries.
4. Each of the following (Q) lines contains a query in one of the two formats:
   • For a maximum query: 0 l r
   • For an update query: 1 l r h

Note: The building indices are 0-indexed.

outputFormat

For each maximum query (queries of type 0) in every test case, output the result on a new line to standard output (stdout). The results should be printed in the order the queries appear.## sample

1
5
1 3 4 2 5
3
0 1 3
1 0 2 3
0 0 4

4
7