Dynamic Maximum Subarray Sum Query

You are given an array of n integers and q queries. The queries are of two types:

1. Update: Change the element at position p to a new value x.
2. Query: Compute the maximum subarray sum in the current array.

The maximum subarray sum is defined as follows:

$$ \max_{1 \leq i \leq j \leq n} \; \sum_{k=i}^{j}a_k $$

If all numbers in the array are negative, then the answer is the maximum (i.e. the least negative) element in the array.

For each query of type 2, output the answer on a new line.

inputFormat

The input is given from standard input in the following format:

The first line contains two integers n and q.

The second line contains n integers denoting the elements of the array.

Each of the next q lines represents a query and is in one of the two formats:

• For an update query: 1 p x where the element at position p is updated to x (1-indexed).
• For a maximum subarray sum query: 2.

outputFormat

For each query of type 2, print a single line containing the maximum subarray sum after performing all operations up to that point.## sample

5 5
1 2 3 -2 5
2
1 2 -10
2
1 3 4
2

9
6
7

</p>