004 - フェーン現象 (Foehn Phenomena)

問題

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

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

• A_i < A_i+1 のとき，標高が 1 上がるごとに風の温度は S 度下がる．
• A_i ≥ A_i+1 のとき，標高が 1 下がるごとに風の温度は T 度上がる．

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

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

課題

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

入力

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

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

出力

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

制限

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

• 1 ≤ N ≤ 200 000．
• 1 ≤ Q ≤ 200 000．
• 1 ≤ S ≤ 1 000 000．
• 1 ≤ T ≤ 1 000 000．
• A₀ = 0．
• −1 000 000 ≤ A_i ≤ 1 000 000 (1 ≤ i ≤ N)．
• 1 ≤ L_j ≤ R_j ≤ N (1 ≤ j ≤ Q)．
• −1 000 000 ≤ X_j ≤ 1 000 000 (1 ≤ j ≤ Q)．

小課題

小課題 1 [30 点]

以下の条件を満たす．

• N ≤ 2 000．
• Q ≤ 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