给你一个长度为 $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$ 。