AT_joi2017ho_a フェーン現象 (Foehn Phenomena)

[problemUrl]: https://atcoder.jp/contests/joi2017ho/tasks/joi2017ho_a

標準入力から以下の入力を読み込め． - $ 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 君の家に吹く風の温度を出力せよ． - - - - - -

### 課題 地殻変動が起きる前の標高と地殻変動の情報が与えられたとき，すべての整数 $ 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 点\] - 追加の制限はない． - - - - - - ### Sample Explanation 1 最初，地点 $ 0,\ 1,\ 2,\ 3 $ の標高はそれぞれ $ 0,\ 4,\ 1,\ 8 $ である．$ 1 $ 日目の地殻変動の後，標高はそれぞれ $ 0,\ 6,\ 3,\ 8 $となる．このとき，地点 $ 0,\ 1,\ 2,\ 3 $ での風の温度はそれぞれ $ 0,\ -6,\ 0,\ -5 $ となる． - - - - - - ### Sample Explanation 2 この入力例は，小課題 $ 2 $ の条件を満たす． - - - - - -