Maximum Subarray Sum with Length Constraint

You are given an integer sequence a of length n and a constant c.

There are m operations. Each operation is one of the following types:

• 1 x y: Update the value at position x to y.
• 2 l r: Query the maximum subarray sum in the range [l, r] with the constraint that the subarray length does not exceed c. Formally, the answer is computed as
  
  $$\max\Biggl(\max_{l \le l' \le r' \le r,\; r'-l'+1 \le c} \;\Bigl(\sum_{i=l'}^{r'} a_i\Bigr) ,\; 0\Biggr)$$
  
  Note that if all valid subarray sums are negative, the answer is 0.

Process all m operations in order.

inputFormat

The first line contains three integers n, m, and c where n is the length of the sequence, m is the number of operations, and c is the maximum allowed subarray length in a query.

The second line contains n integers representing the array a.

The following m lines each contain an operation in one of the following two formats:

• 1 x y: Update operation (set a[x] = y).
• 2 l r: Query operation (find the maximum subarray sum in the interval [l, r] with subarray length at most c).

outputFormat

For each query operation (operation type 2), output a single line containing the answer.

sample

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

7
5
14