Maximum range sum? 1

Interview

Time limit1sMemory limit128 MB

Summary

Maintain an array under point updates. For each range query, find the maximum of U times a subarray sum plus V times its length over all subarrays inside the range.

Level: Medium5 of 10
Topics: Array, Brute force, Prefix sum, Implementation
Solved: No attempts yet

Problem

You are given a sequence $K_1, K_2, \dots, K_N$ of length $N$ and two constants $U$ and $V$ .

There are $Q$ queries of two kinds.

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

Input

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

The second line contains the integers $K_1, K_2, \dots, K_N$ . ( $-10^2 \le K_i \le 10^2$ )

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 and $1 \le A \le B \le N$ . If $C$ is 1, the query is of the second kind and $1 \le A \le N$ , $-10^2 \le B \le 10^2$ .

Output

For each query of the first kind, print its result on its own line.

Examples1

Example 1

Input

Expected output

26
20