Prof. Pang 有 $c$ 天的年假，他想要去度假。

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

Prof. Pang 希望你执行 $m$ 次操作：

• 1 x y：将第 $x$ 天的幸福值修改为 $y$。
• 2 l r：Prof. Pang 想要在 $[l, r]$ 区间内寻找一个度假时段。他希望连续休息若干天（可能为 0 天），并获得尽可能多的幸福值。然而，他只有 $c$ 天假期，因此在 $[l, r]$ 区间内他最多只能连续休息 $c$ 天。

这意味着他想要找到：

$$\max \left( \max_{\substack{l \le l' \le r' \le r \\ r' - l' + 1 \le c}} \left( \sum_{i=l'}^{r'} a_i \right), 0 \right)$$

输入格式

第一行包含三个整数 $n, m, c$ ($1 \le n \le 2 \times 10^5, 1 \le m \le 5 \times 10^5, 1 \le c \le n$)，分别表示一年的天数、操作次数以及 Prof. Pang 的年假天数。

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

接下来 $m$ 行，每行描述一个上述格式的操作。

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

输出格式

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

样例

样例输入 1

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

样例输出 1

8
10
0
5