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 200000$.
• $1\le Q\le 200000$.
• $1\le S\le 1000000$.
• $1\le T\le 1000000$.
• $A_0=0$.
• $-1000000\le A_i\le 1000000$ $(1\le i\le N)$.
• $1\le L_j\le R_j\le N$ $(1\le j\le Q)$.
• $-1000000\le X_j\le 1000000$ $(1\le j\le Q)$.

Subtasks

Subtask 1 [30 points]

The following conditions are satisfied.

• $N\le 2000$.
• $Q\le 2000$.

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