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