Foehn Phenomena

Time Limit : 1 sec, Memory Limit : 262144 KB

フェーン現象(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


Source: 16th Japanese Olympiad in Informatics , 2016-2-11
http://www.ioi-jp.org/