Maximum Sum Subarray

You are given an array of n integers and q queries. There are two types of queries: update array at a given index p, and calculate the maximum sum subarray within a subarray [l; r].
The maximum sum subarray within a subarray [l; r] is defined as the contiguous subarray with the maximum sum of its elements. In other words, you need to find the sum of the subarray [l'; r'] such that the sum of its elements is maximum among all possible non-empty subarrays within the range [l; r].

Input

The first line of the input contains two integers n and q (1 ≀ n, q ≀ 100 000).
The next line contains n space-separated integers ( ≀ ≀ ).
The following q lines contain all the queries - 1 l r (1 ≀ l ≀ r ≀ n) or 2 p x (1 ≀ p ≀ n, ≀ x ≀ ) representing the two types of queries:
  1. Get the maximum sum subarray within a subarray [l; r].
  1. Update the array at position p with value x.

Output

For each query of type 1, the program should print the answer to that query.

Examples

Input
Output
8 4 -2 1 -3 4 -7 2 1 -5 1 2 6 2 5 0 1 2 6 1 1 2
4 6 1
Β 

Constraints

Time limit: 10 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue