Problem: 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 < 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)．$



Sample Input and Output

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


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





Creatie Commons License

The 16th Japanese Olympiad in Informatics (JOI 2016/2017) Final Round





Example

Input

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


Output

-5
-7
-13
-13
-18

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}



class LazySegmentTree{
private:
    int n;
    vector<long long> node, lazy;
    long long node_init = 0; // sum, max, update
    //long long node_init = LINF; // min
    long long lazy_init = 0; // default
    //long long lazy_init = LINF; // min, update (存在しない値)

    long long lazy_update(long long a,long long b){
        return a+b; // sum query
        //return max(a,b); // max query
        //return min(a,b); // min query
        //return b; // update query
    }

    long long node_update(long long a, long long b, int l, int r){ // lazy を node に反映
        return a + b; // min query
        //return b; // update query
        //return b * (r-l); // sum query
    }

    long long combine(long long a,long long b){
        return a+b; // sum query
        //return max(a,b); // max query
        //return min(a,b); // min query
    }

public:
    LazySegmentTree(){}
    LazySegmentTree(vector<long long> in){
        n = 1;
        while(n < in.size())n <<= 1;
        node = vector<long long>(2*n, node_init);
        lazy = vector<long long>(2*n, lazy_init);
        for(int i = n-1+in.size()-1; i >= 0; i--){
            if(n-1 <= i)node[i] = in[i-(n-1)];
            else node[i] = combine(node[i*2+1], node[i*2+2]);
        }
    }
    void eval(int k, int l, int r){
        if(lazy[k] != lazy_init){
            node[k] = node_update(node[k], lazy[k], l, r);
            if(r - l > 1){
                lazy[2*k+1] = lazy_update(lazy[2*k+1], lazy[k]);
                lazy[2*k+2] = lazy_update(lazy[2*k+2], lazy[k]);
            }
            lazy[k] = lazy_init;
        }
    }
    void update(int a, int b, long long x, int k = 0, int l = 0, int r = -1){
        if(r < 0)r = n;
        eval(k,l,r);
        if(b <= l || r <= a)return;
        if(a <= l && r <= b){
            lazy[k] = x;
            eval(k,l,r);
        }else{
            update(a,b,x,2*k+1,l,(l+r)/2);
            update(a,b,x,2*k+2,(l+r)/2,r);
            node[k] = combine(node[2*k+1], node[2*k+2]);
        }
    }
    long long query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0)r = n;
        if(b <= l || r <= a)return node_init;
        eval(k,l,r);
        if(a <= l && r <= b)return node[k];
        return combine(query(a,b,2*k+1,l,(l+r)/2), query(a,b,2*k+2,(l+r)/2,r));
    }
    void show(){
        cout << "node :";
        for(int i = 0; i < 2*n-1; i++){
            if(i == n-1)cout << "     ";
            cout << " " << node[i];
        }
        cout << endl;
        cout << "lazy :";
        for(int i = 0; i < 2*n-1; i++){
            if(i == n-1)cout << "     ";
            cout << " " << lazy[i];
        }
        cout << endl;
    }
};

int f(int a, int b, int s, int t){
    int ret;
    if(a < b)ret = -s * (b - a);
    else ret = t * (a - b);
    return ret;
}


signed main(void) {
    int n,q,s,t;
    cin >> n >> q >> s >> t;
    vi a(n+1);
    rep(i,n+1)cin >> a[i];
    int ans = 0;
    rep(i,n){
        if(a[i] < a[i+1])ans -= s * (a[i+1] - a[i]);
        else ans += t * (a[i] - a[i+1]);
    }
    LazySegmentTree st(a);
    while(q--){
        int l,r,x;
        cin >> l >> r >> x;
        //[l-1, l] と [r, r+1] を変更する
        int al1 = st.query(l-1,l);
        int al2 = st.query(l,l+1);
        int ar1 = st.query(r,r+1);
        int ar2 = st.query(r+1,r+2);
        //cout << "!" << al1 << " " << al2 << " " << ar1 << " " << ar2 << endl;
        ans += f(al1, al2+x, s, t) - f(al1, al2, s, t);
        if(r < n)ans += f(ar1+x, ar2, s, t) - f(ar1, ar2, s, t);
        cout << ans << endl;
        //st.show();
        st.update(l,r+1,x);
    }


}