구간 합 최대? 1

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

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

1. $A$, $B$가 주어지면 $A \le i \le j \le B$를 만족하는 $i$, $j$ 중에서 $U \times (K_i + K_{i+1} + \dots + K_j) + V \times (j - i)$의 최댓값을 구한다.
2. $A$, $B$가 주어지면 $K_A$의 값을 $B$로 바꾼다.

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

둘째 줄에 정수 $K_1, K_2, \dots, K_N$이 주어진다. ($-10^2 \le K_i \le 10^2$)

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

$C$가 0이면 첫 번째 종류의 쿼리이고, 이때 $1 \le A \le B \le N$이다. $C$가 1이면 두 번째 종류의 쿼리이고, 이때 $1 \le A \le N$, $-10^2 \le B \le 10^2$이다.

첫 번째 종류의 쿼리마다 그 결과를 한 줄에 하나씩 출력한다.