フェーン現象(Foehn Phenomena)

IOI 国では海から陸に向かって常に風が吹いている．風は地点0 から地点1，地点2，... という経路を通りながら地点 $N$ まで吹く．地点 $N$ にはJOI 君の家が建てられている．地点0 の標高は $A_0$ = 0 であり，地点 $i$ ($1 \leq i \leq N$) の標高は $A_i$ である．

風は地表面に沿って吹き，高度の変化に応じて風の温度が変化する．海に接している地点0 での風の温度は0 度であり，すべての $i$ ($0 \leq i \leq N - 1$) に対して，地点 $i$ から地点 $i + 1$ にかけての風の温度の変化はその時点における $A_i$ と $A_{i+1}$ にのみ依存しており，以下のようになっている．

• $A_i < A_{i+1}$ のとき，標高が1 上がるごとに風の温度は $S$ 度下がる．
• $A_i \geq A_{i+1}$ のとき，標高が1 下がるごとに風の温度は $T$ 度上がる．

IOI 国の領土では地殻変動が盛んである．あなたは，$Q$ 日間の地殻変動のデータを入手した． $j$ 日目($1 \leq j \leq Q$) には，$L_j \leq k \leq R_j (1 \leq L_j \leq R_j \leq N$) を満たす地点の標高 $A_k$ が $X_j$ だけ変化する．$X_j$ が非負のときは，標高が $X_j$ だけ上がることを意味し，$X_j$ が負のときは，標高が$|X_j|$ だけ下がることを意味する．

あなたの仕事は，各地殻変動が起こった後の，JOI 君の家に吹く風の温度を求めることである．

課題

地殻変動が起きる前の標高と地殻変動の情報が与えられたとき，すべての整数 $j$ ($1 \leq j \leq Q$) に対し， $j$ 日目の地殻変動が起こった後のJOI 君の家に吹く風の温度を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には， 4 個の整数 $N, Q, S, T$ が空白を区切りとして書かれている．これらは，JOI 君の家が地点 $N$ に建てられており，地殻変動の回数が $Q$ であり，標高が1 上がるごとに風の温度が $S$ 度下がり，1 下がるごとに $T$ 度上がることを表す．
• 続く $N + 1$ 行のうちの $i$ 行目($1 \leq i \leq N + 1$) には，地点 $i - 1$ での地殻変動が起こる前の標高を表す整数 $A_{i-1}$ が書かれている．
• 続く $Q$ 行のうちの $j$ 行目($1 \leq j \leq Q$) には，3 個の整数 $L_j, R_j, X_j$ が空白を区切りとして書かれている．これらは， $j$ 日目の地殻変動で地点 $L_j$ から $R_j$ までの標高が $X_j$ だけ変化することを表す．

出力

出力は $Q$ 行からなる．標準出力の $j$ 行目($1 \leq j \leq Q$) には，$j$ 日目の地殻変動が起こった後のJOI 君の家 に吹く風の温度を出力せよ．

制限

すべての入力データは以下の条件を満たす．

• $1 \leq N \leq 200 000．$
• $1 \leq Q \leq 200 000．$
• $1 \leq S \leq 1 000 000．$
• $1 \leq T \leq 1 000 000．$
• $A_0 = 0．$
• $-1 000 000 \leq A_i \leq 1 000 000 (1 \leq i \leq N)．$
• $1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)．$
• $ -1 000 000 \leq X_j \leq 1 000 000 (1 \leq j \leq Q)．$

入出力例

入力例1

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

出力例1

-5
-7
-13
-13
-18

最初，地点0, 1, 2, 3 の標高はそれぞれ0, 4, 1, 8 である．1 日目の地殻変動の後，標高はそれぞれ0, 6, 3, 8 となる．このとき，地点0, 1, 2, 3 での風の温度はそれぞれ0, -6, 0, -5 となる．

入力例2

2 2 5 5
0
6
-1
1 1 4
1 2 8

出力例2

5
-35

入力例3

7 8 8 13
0
4
-9
4
-2
3
10
-9
1 4 8
3 5 -2
3 3 9
1 7 4
3 5 -1
5 6 3
4 4 9
6 7 -10

出力例3

277
277
322
290
290
290
290
370

---