Problem Description

Input Format

Read the following input from standard input:

• The first line contains four integers $N, Q, S, T$ separated by spaces. These represent that JOI's house is built at location $N$, the number of crustal movements is $Q$, the wind temperature drops by $S$ degrees for every increase in altitude, and it rises by $T$ degrees for every decrease in altitude.
• The next $N + 1$ lines contain an integer $A_{i - 1}$ which represents the altitude at location $i + 1$ before any crustal movements occur.
• The next $Q$ lines contain three integers $L_j, R_j, X_j$ separated by spaces. These represent that on the $j$-th day, the altitude from location $L_j$ to $R_j$ changes by $X_j$.

Output Format

Output consists of $Q$ lines. The $j$-th line ($1 \leq j \leq Q$) should contain the wind temperature at JOI's house after the crustal movement on the $j$-th day.

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

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

Notes/Hints

Task

Given the initial altitudes before any crustal movements and the information about the crustal movements, create a program that calculates the wind temperature at JOI's house after each of the $Q$ crustal movements.

Constraints

All input data satisfies 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$).

Subtasks

Subtask 1 [30 points]

Satisfies the following conditions:

• $N \leq 2,000$.
• $Q \leq 2,000$.

Subtask 2 [10 points]

• Satisfies $S = T$.

Subtask 3 [60 points]

• No additional restrictions.

Sample Explanation 1

Initially, the altitudes at locations $0, 1, 2, 3$ are $0, 4, 1, 8$ respectively. After the first day's crustal movement, the altitudes become $0, 6, 3, 8$. At this time, the wind temperatures at locations $0, 1, 2, 3$ are $0, -6, 0, -5$ respectively.

Sample Explanation 2

This input example satisfies the conditions of Subtask 2.

见题面 Input 部分

见题面 Output 部分