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

時間制限 1 秒 / メモリ制限 256 MB / 得点 1 / x 0 /


TLE
1sec
MLE
256MB
得点
1

問題

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

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

  • Ai < Ai+1 のとき,標高が 1 上がるごとに風の温度は S 度下がる.
  • AiAi+1 のとき,標高が 1 下がるごとに風の温度は T 度上がる.

IOI 国の領土では地殻変動が盛んである.あなたは,Q 日間の地殻変動のデータを入手した.j 日目(1 ≤ jQ) には,LjkRj(1 ≤ LjRjN) を満たす地点の標高 AkXj だけ変化する.Xj が非負のときは,標高が Xj だけ上がることを意味し,Xj が負のときは,標高が |Xj| だけ下がることを意味する.

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

課題

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

入力

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

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

出力

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

制限

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

  • 1 ≤ N ≤ 200 000.
  • 1 ≤ Q ≤ 200 000.
  • 1 ≤ S ≤ 1 000 000.
  • 1 ≤ T ≤ 1 000 000.
  • A0 = 0.
  • −1 000 000 ≤ Ai ≤ 1 000 000 (1 ≤ iN).
  • 1 ≤ LjRjN (1 ≤ jQ).
  • −1 000 000 ≤ Xj ≤ 1 000 000 (1 ≤ jQ).

小課題

小課題 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