No submission language available for this problem.

Background

时空管理员小 A 所带领的队伍遇到了时空王级灾兽，他需要调整战斗人员的输出能级，用以攻击灾兽的弱点。

Description

队伍中除小 A 以外，有 N 人，他们的输出能级用 A[1] 到 A[N] 表示，第 i 个人的输出能级为 A[i] $(0\le i \le N)$。

小 A 作为组织者，为了配合集体的能级波动，他永远站在第一个位置，输出能级用 A[0] 表示，且 A[0] 永远为 0

小 A 将组织 Q 次进攻，每次进攻前，将会对 [L, R] 队员的输出能级进行调整，调整值为 Z。(Z 可正可负)

整体队伍的能级 B 的计算办法是：

初始 B = 0，然后从 1 号到 N 号队员有，

• 当$A_{i-1}<A_i$：$B = B-S\cdot|A_{i-1} - A_i|$
• 当$A_{i-1}>A_i$：$B = B+T\cdot|A_{i-1} - A_i|$

其中 S 和 T 是两个能级常数。

请输出每次进攻时，队伍能级 B

Format

Input

一行 4 个整数，N，Q，S，T，分别表示队伍人的个数，进攻次数以及两个能级常数

之后的 N+1 行，每行一个数整数 Ai，其中 A0 = 0

最后的 Q 行，每行 3 个整数，L，R，Z 表示每次进宫前，对 [L, R] 的队员进行能级调整，调整值为 Z

Output

Q 个整数，表示答案。

Samples

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

-9
-1
-5

Limitation

30% 的数据 $N,Q\le 2000$

100%的数据 $N,Q\le 200000$；$1\le S,T,A_i\le10^6$；$|Z|\le 10^6$ 请注意可能需要使用 int64

样例解释：

第一次变化后，

A 0 6 3 4 6

B -12 -3 -5 -9