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

Time Limit: 1 sec / Memory Limit: 256 MB

配点 : 100

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

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

  • A_i \lt A_{i+1} のとき,標高が 1 上がるごとに風の温度は S 度下がる.
  • A_i ≧ A_{i+1} のとき,標高が 1 下がるごとに風の温度は T 度上がる.

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

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

課題

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


入力

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

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

出力

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


制限

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

  • 1 ≦ N ≦ 200\,000
  • 1 ≦ Q ≦ 200\,000
  • 1 ≦ S ≦ 1\,000\,000
  • 1 ≦ T ≦ 1\,000\,000
  • A_0 = 0
  • -1\,000\,000 ≦ A_i ≦ 1\,000\,000 (1 ≦ i ≦ N)
  • 1 ≦ L_j ≦ R_j ≦ N (1 ≦ j ≦ Q)
  • -1\,000\,000 ≦ X_j ≦ 1\,000\,000 (1 ≦ j ≦ Q)

小課題

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

Score : 100 points

In the Kingdom of IOI, the wind always blows from sea to land. There are N + 1 spots numbered from 0 to N. The wind from Spot 0 to Spot N in order. Mr. JOI has a house at Spot N. The altitude of Spot 0 is A_0 = 0, and the altitude of Spot i (1 \leq i \leq N) is A_i .

The wind blows on the surface of the ground. The temperature of the wind changes according to the change of the altitude. The temperature of the wind at Spot 0, which is closest to the sea, is 0 degree. For each i (0 \leq i \leq N − 1), the change of the temperature of the wind from Spot i to Spot i + 1 depends only on the values of A_i and A_{i+1} in the following way:

  • If A_i \lt A_{i+1} , the temperature of the wind decreases by S degrees per altitude.
  • If A_i \geq A_{i+1} , the temperature of the wind increases by T degrees per altitude.

The tectonic movement is active in the land of the Kingdom of IOI. You have the data of tectonic movements for Q days. In the j-th (1 \leq j \leq Q) day, the change of the altitude of Spot k for L_j \leq k \leq R_j (1 \leq L_j \leq R_j \leq N) is described by X_j . If X_j is not negative, the altitude increases by X_j . If X_j is negative, the altitude decreases by |X_j|.

Your task is to calculate the temperature of the wind at the house of Mr. JOI after each tectonic movement.

Task

Given the data of tectonic movements, write a program which calculates, for each j (1 \leq j \leq Q). the temperature of the wind at the house of Mr. JOI after the tectonic movement on the j-th day.


Input

Read the following data from the standard input.

  • The first line of input contains four space separated integers N,Q,S,T. This means there is a house of Mr. JOI at Spot N, there are Q tectonic movements, the temperature of the wind decreases by S degrees per altitude if the altitude increases, and the temperature of the wind increases by T degrees per altitude if the altitude decreases.
  • The i-th line (1 \leq i \leq N+1) of the following N+1 lines contains an integer A_{i−1} , which is the initial altitude at Spot (i − 1) before tectonic movements.
  • The j-th line (1 \leq j \leq Q) of the following Q lines contains three space separated integers L_j, R_j, X_j. This means, for the tectonic movement on the j-th day, the change of the altitude at the spots from L_j to R_j is described by X_j.

Output

Write Q lines to the standard output. The j-th line (1 \leq j \leq Q) of output contains the temperature of the wind at the house of Mr. JOI after the tectonic movement on the j-th day.

Constraints

All input data satisfy the following conditions.

  • 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).

Subtask

Subtask 1 [30 points]

The following conditions are satisfied.

  • N \leq 2\,000.
  • Q \leq 2\,000.

Subtask 2 [10 points]

  • S = T.

Subtask 3 [60 points]

There are no additional constrains.

Sample Input 1

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

Sample Output 1

-5
-7
-13
-13
-18

Initially, the altitudes of the spot 0,1,2,3 are 0, 4, 1, 8, respectively. After the tectonic movement on the first day, the altitudes become 0, 6, 3, 8, respectively. At that moment, the temperatures of the wind are 0, -6, 0, 5, respectively.


Sample Input 2

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

Sample Output 2

5
-35

This sample input satisfies the constrains of Subtask 2.


Sample Input 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

Sample Output 3

277
277
322
290
290
290
290
370