Description

我们Aqours的成员共有N+1人，他们会列成一队。

他们的唱功以A[0]到A[N]表示，A[i]$(0\le i \le N)$均给出。

学园都市的机器可以改变队列中连续多个成员的唱功值，并将其加上一个数Z，当然当Z是负数的时候就变成减去了。

我打算一共使用这个机器Q次，每次把第X到第Y号（$1\le X,Y\le10^6$）的成员都加上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是LoveLive组委会给我们的常数。

果然，我是バカチカ（笨蛋千歌）呢，所以作为领导我永远排在队伍的开头，唱功永远是0，机器也不会改到我头上呢。

你能帮我们算算，我每次使用完这个机器之后，成员的魅力B是多少吗？

Input Format

第一行4个整数，N，Q，S，T，各个变量在描述中已经解释

接下来N+1行，每行一个数整数Ai，其中A0=0

接下来Q行，每行3个整数，X，Y，Z各个变量在描述中已经解释

Output Format

Q个整数，表示答案。

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

-9
-1
-5

Hint

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

另外20% 的数据 $S=T$

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

样例解释：

第一次变化后，

A 0 6 3 4 6

B -12 -3 -5 -9

以下是彩蛋

没有。

哪来的那么多彩蛋？