Vacation Happiness

Prof. Pang has an annual leave of \(c\) days and he wants to go on vacation. There are \(n\) days in a year and each day \(i\) provides a happiness value \(a_i\) (which may be negative if the day is not so enjoyable). Prof. Pang will perform \(m\) operations of the following two types:

• Type 1 (Update): 1 x y — change the happiness of the \(x\text{-th}\) day to \(y\).
• Type 2 (Query): 2 l r — consider the subarray \([l, r]\) and determine the maximum total happiness that can be obtained by choosing a contiguous block of days with length at most \(c\). Formally, find \[ \max\Biggl(\max_{l \le l' \le r' \le r \atop r'-l'+1 \le c}\left(\sum_{i=l'}^{r'} a_i\right),\; 0\Biggr). \] This means if all subarrays yield a negative sum, output \(0\) (since he may choose to not take any vacation days).

Your task is to process the \(m\) operations and for each query of type 2, output the answer.

inputFormat

The input begins with a line containing three integers \(n\), \(c\), and \(m\) separated by spaces.

The next line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces, representing the happiness values on each day.

The following \(m\) lines each represent an operation in one of the following formats:

• 1 x y: Update operation; set \(a_x = y\).
• 2 l r: Query operation; compute and output the maximum happiness obtainable from a contiguous subarray (of length at most \(c\)) within the range \([l, r]\).

outputFormat

For each query of type 2, output a single integer on a new line representing the maximum achievable happiness as defined. (Remember, if no positive sum can be obtained, the answer is \(0\)).

sample

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

3
8
13