Background

What kind of future it is, nobody knows yet.

But it should be fun.

If we’re all together, we can overcome anything.

It’s just the beginning—let’s encourage each other.

What kind of future it is, nobody knows yet.

But I really hope it will be full of fun.

If we’re all together, we’ll even want to push our limits.

I want to grow—I’m still just an immature DREAMER.

The members of Aqours have finally gathered.

Today is our very first concert with everyone together.

Everyone has practiced well; I’m sure we’ll perform great.

However, everyone’s singing skills should be as close as possible. If someone is too outstanding or too far behind, it will affect the performance.

So we borrowed an invention from the neighboring Academy City that can change our members’ singing skills.

Problem Description

There are $N+1$ members in Aqours, lined up in a row.

Their singing skills are denoted by $A[0]$ to $A[N]$, and all $A[i]$ for $0 \le i \le N$ are given.

The machine from Academy City can change the singing skills of a consecutive segment in the line by adding a number $Z$ to each of them. Of course, if $Z$ is negative, it means subtracting.

I plan to use this machine $Q$ times. Each time, I add $Z$ to the singing skills of all members from index $X$ to index $Y$ (with $1 \le X, Y \le 10^6$).

Our team’s charm value $B$ is computed as follows:

Initially, $B = 0$. Then, for members from index $1$ to $N$:

• If $A_{i-1} < A_i$: $B = B - S \cdot |A_{i-1} - A_i|$.
• If $A_{i-1} > A_i$: $B = B + T \cdot |A_{i-1} - A_i|$.

Here $S$ and $T$ are constants given by the Love Live committee.

As the leader, I (Chika) am always at the front of the line, with singing skill always $0$. The machine will never modify me. Thus $A_0 = 0$ at all times.

Can you help us compute the charm value $B$ after each use of the machine?

Input Format

• The first line contains four integers $N$, $Q$, $S$, $T$ (as described above).
• The next $N+1$ lines each contain one integer $A_i$, with $A_0 = 0$.
• The next $Q$ lines each contain three integers $X$, $Y$, $Z$ (as described above).

Output Format

Output $Q$ integers, one per line, where the $i$-th line is the value of $B$ after the $i$-th operation.

4 3 2 3
0
5
2
4
6
1 2 1
3 4 -3
1 4 2

-9
-1
-5

Hint

• For 30% of the testdata, $N, Q \le 2000$.
• Additionally, for another 20% of the testdata, $S = T$.
• For 100% of the testdata, $N, Q \le 200000$; $1 \le S, T, A_i \le 10^6$; $|Z| \le 10^6$.
• Note that a 64-bit integer may be required, and using std::cin/std::cout may time out.

Explanation of the sample:

After the first change,

A: 0 6 3 4 6

B: -12 -3 -5 -9

Easter egg:

None.

Why would there be so many easter eggs?

Translated by ChatGPT 5