该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

D

给你一个长度为 $n$ 的正整数序列 $a$，和一个常数 $c$ 。

定义 $S[l,r]$ 表示区间 $[l,r]$ 的和。

有 $m$ 次操作：

1 x y：将位置 $x$ 的值修改为 $y$。

2 l r：表示询问区间 $[l,r]$ 中，对于所有子区间 $[l',r']$ 满足 $l\le l'\le r'\le r$ 且 $r'-l'+1\le c$，最大的 $S[l',r']$。

输入格式

第一行三个正整数 $n,m,c$ ，分别表示序列长度，操作次数，以及给定的常数。

之后一行 $n$ 个整数 $a_1,\dots,a_n$ 表示序列 $a$ 。

之后 $m$ 行，每行三个数表示一次操作，意义如上述。

输出格式

对每个询问，输出一行一个数表示答案。

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

数据范围

对于 $25\%$ 的数据，$n,m\le 10^3$。

对于另外 $25\%$ 的数据，$n\le 10^6,m\le 2\times 10^6$，只有询问操作。

对于另外 $25\%$ 的数据，$n\le 10^6, m\le 2\times 10^6$。

对于 $100\%$ 的数据，$1 \le n, m\le 2\times 10^6, 1\le x\le n, 1\le l\le r\le n, -10^9 \le a_i,y \le 10^9$ 。