問題文

IOI 国では海から陸に向かって常に風が吹いている．風は地点 $0$ から地点 $1$，地点 $2$，... という経路を通りながら地点 $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 \leq 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 \leq j \leq Q)$ には，$j$ 日目の地殻変動が起こった後の JOI 君の家 に吹く風の温度を出力せよ．

3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5

-5
-7
-13
-13
-18

2 2 5 5
0
6
-1
1 1 4
1 2 8

5
-35

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

277
277
322
290
290
290
290
370

制限

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

• $1\leqq N, Q\leqq 2\times 10^5$
• $1\leqq S, T\leqq 10^6$
• $A_0=0,$ $|A_i|\leqq 10^6$ $(1\leqq i\leqq N)$
• $1\leqq L_j\leqq R_j\leqq N$
• $|X_j|\leqq 10^6$ $(1\leqq j\leqq Q)$

小課題

小課題 1 [30 点] $\quad$ $N, Q\le 2000$ を満たす．
小課題 2 [10 点] $\quad$ $S=T$ を満たす．
小課題 3 [60 点] $\quad$ 追加の制限はない．