Problem Description

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

There are $m$ operations:

1 x y: Modify the value at position $x$ to $y$.

2 l r: Query $\max\left(\max_{l \leq l' \leq r' \leq r\atop r'-l'+1\leq c} ~~ \left(\sum_{i=l'} ^{r'} a_i\right), 0\right)$ within the interval $[l,r]$.

Input Format

The first line contains three positive integers $n, m, c$, representing the length of the sequence, the number of operations, and the given constant.

The next line contains $n$ integers $a_1,\dots,a_n$, representing the sequence $a$.

Then follow $m$ lines, each containing three numbers describing one operation, with the meaning as stated above.

Output Format

For each query, output one line with one number representing the answer.

5 10 2
0 -5 -3 8 -3
1 5 -1
1 2 3
1 5 -6
1 2 9
2 5 5
2 3 3
1 1 -3
2 4 4
1 1 4
1 3 3

0
0
8

Hint

Idea: chenkuowen&nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For $100\%$ of the testdata, $1 \le n\le 10^6$, $1\le m\le 2\times10^6$, $1\le x,c\le n$, $1\le l\le r\le n$, $-10^9 \le a_i,y \le 10^9$.

Translated by ChatGPT 5