Query Processor

You are given an array of n integers. Your task is to process q queries of three types.

• update i x: Update the i-th element (1-indexed) of the array to x.
• sum l r: Compute the sum $$\sum_{i=l}^{r} a_i$$ in the subarray from index l to r (inclusive).
• max l r: Find the maximum element in the subarray from index l to r (inclusive).

After processing all queries, print the results for the sum and max operations in the order they appear (each on its own line). Note that the update queries do not produce any output.

inputFormat

The first line contains two space-separated integers n and q --- the number of elements and the number of queries respectively.

The second line contains n space-separated integers, representing the initial state of the array.

Each of the next q lines contains one query in one of the following formats:

• update i x
• sum l r
• max l r

outputFormat

For every sum or max query, output the result on a new line in the order of appearance.

## sample

8 5
1 3 5 7 9 2 4 6
update 4 10
sum 2 5
max 3 7
sum 1 8
max 1 8

27
10
40
10

</p>