Segment Tree with Lazy Propagation

In this problem, you are given an array of integers and a sequence of operations. There are two types of operations: update and query. For an update operation, you will add a value to all the elements in a specified subarray, and for a query operation, you must report the maximum value in a given subarray. You are required to implement a segment tree with lazy propagation to handle these operations efficiently.

More formally, let (A = [a_1, a_2, \dots, a_n]) be the initial array. Then you will be given (m) operations. Each operation is one of the following forms:

1. Update: (1\ i\ j\ v) - add (v) to each element from index (i) to index (j) (inclusive).
2. Query: (2\ i\ j) - output (\max{a_i, a_{i+1}, \dots, a_j}).

Your solution must read input from stdin and write output to stdout. It is guaranteed that the indices are 1-indexed and that there is at least one query operation.

inputFormat

The input is given via standard input (stdin) and has the following format:

(n) (a_1\ a_2\ \dots\ a_n) (m) (op_1) (op_2) (\dots) (op_m)

Where:

• (n) is the number of elements in the array.
• The next line contains (n) integers representing the array (A).
• (m) is the number of operations.
• Each of the next (m) lines represents an operation. An operation is of the form:
  • For update: 1 i j v
  • For query: 2 i j

All indices (i) and (j) are 1-indexed.

outputFormat

For each query operation, output the maximum value in the requested subarray on a separate line to stdout.## sample

5
1 3 5 7 9
3
2 1 5
1 2 4 3
2 2 4

9
10