길이 N의 수열 K₁, K₂, ..., K_N과 상수 U, V가 주어진다.</p>

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

1. A, B가 주어지면, max(U × (K_i + K_i + 1 + ... + K_j) + V × (j - i)) (A ≤ i ≤ j ≤ B) 의 값을 구한다.
2. A, B가 주어지면, K_A의 값을 B으로 바꾼다.

첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 10³,  - 5 ≤ U, V ≤ 5)

두 번째 줄에 정수 K₁, K₂, ..., K_N이 주어진다. ( - 10² ≤ K_i ≤ 10²)

세 번째 줄부터 쿼리가 주어진다. 세 수 C, A, B가 주어진다. (1 ≤ A, B ≤ N, 0 ≤ C ≤ 1)

C가 0이면 첫 번째 쿼리를, 아니면 두 번째 쿼리를 수행한다. 첫 번째 쿼리일 경우 1 ≤ A ≤ B ≤ N 이다. 두 번째 쿼리일 경우 1 ≤ A ≤ N,  - 10² ≤ B ≤ 10²이다.

출력 형식

한 줄마다 첫 번째 쿼리의 결과값을 출력한다.

예제 입력

5 3 2 4
1 1 1 1 1
0 1 5
1 3 -2
0 1 5

예제 출력

26
20