구간 합 최대 2

길이가 $N$인 정수 수열 $K_1, K_2, \ldots, K_N$과 상수 $U$, $V$가 주어진다.

쿼리 $Q$개가 주어지며, 종류는 두 가지다.

1. $A$, $B$가 주어지면 $A \le i \le j \le B$인 모든 $(i, j)$에 대해 $U \times (K_i + K_{i+1} + \cdots + K_j) + V \times (j - i)$의 최댓값을 구한다.
2. $A$, $B$가 주어지면 $K_A$의 값을 $B$로 바꾼다.

첫째 줄에 정수 $N$, $Q$, $U$, $V$가 주어진다. ($1 \le N, Q \le 10^5$, $-5 \le U, V \le 5$)

둘째 줄에 정수 $K_1, K_2, \ldots, K_N$이 주어진다. ($-100 \le K_i \le 100$)

셋째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 각 줄에는 세 정수 $C$, $A$, $B$가 주어진다. ($0 \le C \le 1$)

$C$가 0이면 첫 번째 종류의 쿼리이고, 아니면 두 번째 종류의 쿼리다. 첫 번째 종류의 쿼리에서는 $1 \le A \le B \le N$이다. 두 번째 종류의 쿼리에서는 $1 \le A \le N$, $-100 \le B \le 100$이다.

첫 번째 종류의 쿼리마다 그 결과를 한 줄에 하나씩 주어진 순서대로 출력한다.