Carbonara

Cerință

În ultima seară a taberei de informatică Hunedoara se servesc paste carbonara. Bucătarul lipsește în mod misterios, dar BIP și Tornada sunt pregătiți să salveze ziua. Ei v-au pregătit $N$ porții de paste carbonara.

Porțiile au diferite valori de gust notate cu $v_1$, $v_2$, …, $v_n$. Din păcate, Tornada și-a scăpat șlapul în ceaun, iar BIP le-a uitat pe foc, așa că unele valori pot fi negative.

Inspirată de apetitul extraordinar al Meșterului din a doua zi, Livlivi s-a decis să-i bată recordul. Ea va alege o subsecvență de porții consecutive $i$, $i+1$, …, $i+k-1$, unde $k > 0$, și le va mânca. Calitatea cinei este egală cu $v_i + v_{i+1} + \dots + v_{i+k-1} – k \cdot P$, unde $P$ reprezintă “penalizarea de lăcomie” și se dă în input.

Pentru că problema ar fi prea ușoară altfel, va trebui să procesați $Q$ interogări care pot fi de două tipuri:

• ”$1$ $i$ $x$”: schimbă valoarea de gust a porției $i$ în $x$ ($v_i$ devine $x$)
• ”$2$ $l$ $r$”: afișează calitatea maximă a unei cine formată doar din porții incluse în intervalul $[l, r]$

Date de intrare

Pe prima linie se vor afla trei numere $N$, $Q$ și $P$, numărul de porții, numărul de interogări și, respectiv, penalizarea de lăcomie. Pe următoarea linie se vor afla $N$ valori $v_1$, $v_2$, …, $v_N$, valorile de gust inițiale a celor $N$ porții.

Pe următoarele $Q$ linii se vor afla interogările în formatul descris în enunț.

Date de ieșire

Pe linia $i$ se va afișa răspunsul la a $i$-a interogare de tipul 2.

Restricții și precizări

• $1 \leq N, Q \leq 100.000$
• $0 \leq P \leq 10$
• $-10^9 \leq v_i \leq 10^9$, pentru orice $1 \leq i \leq N$

Subtask-uri

Exemple

Intrare

5 3 2
11 -6 12 -1 -9
2 1 4
1 1 9
2 1 4

Ieșire

11
10

Explicația exemplului

Pentru prima interogare de tipul 2, cina maximă este formată din porțiile $1$, $2$ și $3$, care formează o cină de calitate $11 + (-6) + 12 – 3 \cdot 2 = 11$.
Pentru cea de-a doua interogare de tipul 2, cina maximă este formată din porția $3$, care formează o cină de calitate $12 – 1 \cdot 2 = 10$