Maximum Interval Sum 2

You are given an integer sequence $K_1, K_2, \ldots, K_N$ of length $N$ and two constants $U$ and $V$.

There are $Q$ queries of two kinds.

1. Given $A$ and $B$, find the maximum of $U \times (K_i + K_{i+1} + \cdots + K_j) + V \times (j - i)$ over all pairs $(i, j)$ with $A \le i \le j \le B$.
2. Given $A$ and $B$, set the value of $K_A$ to $B$.

The first line contains the integers $N$, $Q$, $U$, and $V$. ($1 \le N, Q \le 10^5$, $-5 \le U, V \le 5$)

The second line contains the integers $K_1, K_2, \ldots, K_N$. ($-100 \le K_i \le 100$)

Each of the next $Q$ lines contains one query as three integers $C$, $A$, and $B$. ($0 \le C \le 1$)

If $C$ is 0 the query is of the first kind, otherwise it is of the second kind. For a query of the first kind, $1 \le A \le B \le N$. For a query of the second kind, $1 \le A \le N$ and $-100 \le B \le 100$.

For each query of the first kind, print its result on its own line, in the order the queries are given.