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~ are 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 \le i \le N~) is ~A_i~.

The wind blows on the surface of the ground. The temperature of the wind changes according to the change in altitude. The temperature of the wind at Spot ~0~, which is closest to the sea, is ~0~ degrees. For each ~i~ (~0 \le i \le 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 < A_{i+1}~, the temperature of the wind decreases by ~S~ degrees per altitude.
• If ~A_i \ge 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 \le j \le Q~) day, the change of the altitude of Spot ~k~ for ~L_j \le k \le R_j~ (~1 \le L_j \le R_j \le 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.

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

Input Specification

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 \le i \le 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 \le j \le 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 Specification

Write ~Q~ lines to the standard output. The ~j~-th line (~1 \le j \le 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 \le N \le 200\,000~.
• ~1 \le Q \le 200\,000~.
• ~1 \le S \le 1\,000\,000~.
• ~1 \le T \le 1\,000\,000~.
• ~A_0 = 0~.
• ~-1\,000\,000 \le A_i \le 1\,000\,000~ ~(1 \le i \le N)~.
• ~1 \le L_j \le R_j \le N~ ~(1 \le j \le Q)~.
• ~-1\,000\,000 \le X_j \le 1\,000\,000~ ~(1 \le j \le Q)~.

Subtasks

Subtask 1 [30 points]

The following conditions are satisfied.

• ~N \le 2\,000~.
• ~Q \le 2\,000~.

Subtask 2 [10 points]

• ~S = T~.

Subtask 3 [60 points]

No additional constraints.

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

Sample Input 2

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

Sample Output 2

5
-35