Description

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 thealtitude 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 ofthe 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<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.

Task

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

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 altitudeat 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

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

Sample 1

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

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.

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

5
-35

This sample input satisfies the constraints of Subtask 2.

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

Constraints

All input data satisfy the following conditions:

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

Subtask

Subtask 1: 30 pts $\quad$ $N, Q\le 2000$
Subtask 2: 10 pts $\quad$ $S=T$
Subtask 3: 60 pts $\quad$ No additional constraints.