A - フェーン現象 (Foehn Phenomena) 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

配点： 100 点

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