给你一个长度为 $n$ 的整数序列 $a$，和一个常数 $c$ 。
有 $m$ 次操作：
1 x y：将位置 $x$ 的值修改为 $y$。
2 l r：表示询问区间 $[l,r]$ 中 $\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)$。
输入格式
第一行三个正整数 $n,m,c$ ，分别表示序列长度，操作次数，以及给定的常数。
之后一行 $n$ 个整数 $a_1,\dots,a_n$ 表示序列 $a$ 。
之后 $m$ 行，每行三个数表示一次操作，意义如上述。
输出格式
对每个询问，输出一行一个数表示答案。
样例数据
样例 1 输入
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
样例 1 输出
0 0 8
子任务
Idea：chenkuowen&nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078
对于 $100\%$ 的数据，$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$ 。