Building Height Queries

You are given an array of n building heights. Your task is to process q queries on this array. There are three types of queries:

• Type 1: Increase the height of the x-th building by y.
• Type 2: Decrease the height of the x-th building by y.
• Type 3: Output the maximum height among the buildings in the range from x to y (inclusive).

The result for a type 3 query is mathematically defined as \[ \max_{i=x}^{y} \text{height}_i \] in \(\LaTeX\) format.

All queries must be processed sequentially. Updates made by queries of type 1 and 2 will affect subsequent queries. For each type 3 query, you should output the maximum height on a new line.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers n and q -- the number of buildings and the number of queries.
2. The second line contains n integers, representing the initial heights of the buildings.
3. Each of the next q lines contains three integers t, x, and y, representing a query. For a query of type 1, add y to the height of the x-th building; for type 2, subtract y from it; and for type 3, print the maximum height in the range from x to y (inclusive).

outputFormat

For each query of type 3, output the maximum building height found in the specified range. Each result should be printed on a separate line to stdout.

## sample

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

6
6
6

</p>