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

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

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

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

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

課題

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

---

入力

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

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

出力

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

---

制限

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

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

小課題

小課題 1 [30 点]

以下の条件を満たす．

• $N \\leqq 2\\,000$．
• $Q \\leqq 2\\,000$．

小課題 2 [10 点]

• $S = T$ を満たす．

小課題 3 [60 点]

• 追加の制限はない．

---

入力例 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

この入力例は，小課題 $2$ の条件を満たす．

---

入力例 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