F. Vacation
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Prof. Pang has an annual leave of $$$c$$$ days and he wants to go on vacation.

Now there are $$$n$$$ days in a year. Prof. Pang can gain $$$a_i$$$ happiness if he rests on the $$$i$$$-th day. The values of happiness, $$$a_i$$$, may be negative.

Prof. Pang wants you to do $$$m$$$ operations:

  • $$$1~x~y$$$, change the happiness of the $$$x$$$-th day to $$$y$$$.
  • $$$2~l~r$$$, Prof. Pang wants to find a period of vacation in $$$[l, r]$$$. He wants to rest for several (possibly $$$0$$$) days in a row and gain as much happiness as possible. However, he only has $$$c$$$ days off, thus he can rest for no more than $$$c$$$ consecutive days in $$$[l,r]$$$.

    That means he wants to find $$$$$$\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

The first line contains three integers $$$n, m, c (1\leq n\leq 2\times 10^5, 1\leq m \leq 5\times 10^5, 1\leq c\leq n)$$$ indicating the number of days in a year, the number of operations, and Prof. Pang's annual leave days.

The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n(-10^9 \leq a_i\leq 10^9)$$$ indicating the values of happiness of every day.

The next $$$m$$$ lines are the $$$m$$$ operations in the format described above.

It is guaranteed that $$$1\leq x\leq n, -10^9\leq y\leq 10^9, 1\leq l\leq r \leq n$$$.

Output

For each operation of the second type, print the answer.

Example
Input
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
Output
8
10
0
5