Description

庞教授有 $c$ 天的年假，他想去度假。

现在一年有 $n$ 天。如果庞教授在第 $i$ 天休息，他可以获得 $a_i$ 的幸福感。幸福感的值 $a_i$ 可能是负数。

庞教授希望你执行 $m$ 个操作：

• $1~x~y$，将第 $x$ 天的幸福感改为 $y$。
• $2~l~r$，庞教授希望在 $[l, r]$ 期间找到一个度假期。他希望连续休息几天（可能为 $0$ 天）并获得尽可能多的幸福感。然而，他只有 $c$ 天的假期，因此在 $[l,r]$ 中他最多只能连续休息 $c$ 天。

这意味着他希望找到

$$\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)。$$

Input Format

第一行包含三个整数 $n, m, c (1\leq n\leq 2\times 10^5, 1\leq m \leq 5\times 10^5, 1\leq c\leq n)$，表示一年中的天数、操作的数量和庞教授的年假天数。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n(-10^9 \leq a_i\leq 10^9)$，表示每一天的幸福感值。

接下来的 $m$ 行是格式如上所述的 $m$ 个操作。

保证 $1\leq x\leq n, -10^9\leq y\leq 10^9, 1\leq l\leq r \leq n$。

Output Format

对于每个第二类操作，输出答案。

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

8
10
0
5

Hint

题面翻译由 ChatGPT-4o 提供。