Delivery Zones Query

You are given n delivery zones, each with an initial weight. You need to process m queries on these zones. There are three types of queries:

• 1 i x: Update the weight of the i-th delivery zone to x.
• 2 l r: Compute the sum of weights from zone l to zone r. In mathematical terms, compute $$\sum_{i=l}^{r} w_i$$.
• 3 l r: Find the maximum weight among zones from l to r, i.e., compute $$\max_{l\le i\le r} w_i$$.

Note that the zones are 1-indexed. Only queries of type 2 and 3 require you to output a result. Process the queries in the given order.

inputFormat

The first line contains two integers n and m ((1 \le n, m \le 10^5)), representing the number of delivery zones and the number of queries, respectively.

The second line contains n integers, where the i-th integer denotes the initial weight of the i-th delivery zone.

Each of the following m lines contains a query in one of the following formats:
- 1 i x: Update the i-th zone's weight to x.
- 2 l r: Output the sum of weights for zones between indices l and r (inclusive).
- 3 l r: Output the maximum weight among zones between indices l and r (inclusive).

outputFormat

For each query of type 2 or 3, output the corresponding result on a new line in the order they appear.## sample

6 5
10 20 15 30 25 5
2 1 3
3 2 5
1 4 35
2 1 6
3 3 6

45
30
110
35