Foehn Phenomena

In the Kingdom of IOI, the wind always blows from the sea toward the land. There are $N + 1$ spots, numbered from 0 to $N$. The wind blows from Spot 0 to Spot $N$ in order of their numbers. Mr. JOI has a house at Spot $N$. The altitude of Spot 0 is $A_0 = 0$, and the altitude of Spot $i$ ($1 \le i \le N$) is $A_i$.

The wind blows along the surface of the ground, and its temperature changes as the altitude changes. At Spot 0, which is closest to the sea, the temperature of the wind is 0 degrees. For each $i$ ($0 \le i \le N - 1$), the change in the temperature of the wind from Spot $i$ to Spot $i + 1$ depends only on $A_i$ and $A_{i+1}$, as follows.

• If $A_i < A_{i+1}$, the temperature of the wind decreases by $S$ degrees per unit of altitude, that is, by $S \times (A_{i+1} - A_i)$ degrees.
• If $A_i \ge A_{i+1}$, the temperature of the wind increases by $T$ degrees per unit of altitude, that is, by $T \times (A_i - A_{i+1})$ degrees.

Tectonic movement is active in the land of the Kingdom of IOI. You are given the record of tectonic movements over $Q$ days. On day $j$ ($1 \le j \le Q$), the altitude of every Spot $k$ with $L_j \le k \le R_j$ changes by $X_j$ ($1 \le L_j \le R_j \le N$). If $X_j$ is not negative, the altitude increases by $X_j$. If $X_j$ is negative, the altitude decreases by $|X_j|$. Each tectonic movement applies to the altitudes left by the movements of the previous days.

Given the record of tectonic movements, write a program that computes, for each $j$ ($1 \le j \le Q$), the temperature of the wind at Mr. JOI's house right after the tectonic movement on day $j$.

The first line contains four space-separated integers $N$, $Q$, $S$, and $T$. Mr. JOI's house is at Spot $N$, and there are $Q$ tectonic movements. When the altitude rises, the temperature of the wind decreases by $S$ degrees per unit of altitude. When the altitude falls, it increases by $T$ degrees per unit of altitude.

The $i$-th of the next $N + 1$ lines ($1 \le i \le N + 1$) contains an integer $A_{i-1}$, the altitude of Spot $(i - 1)$ before any tectonic movement.

The $j$-th of the next $Q$ lines ($1 \le j \le Q$) contains three space-separated integers $L_j$, $R_j$, and $X_j$. They mean that on day $j$ the altitude of the spots from $L_j$ to $R_j$ changes by $X_j$.

Print $Q$ lines. The $j$-th line ($1 \le j \le Q$) contains the temperature of the wind at Mr. JOI's house right after the tectonic movement on day $j$.

• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $1 \le S \le 1\,000\,000$
• $1 \le T \le 1\,000\,000$
• $A_0 = 0$
• $-1\,000\,000 \le A_i \le 1\,000\,000$ ($1 \le i \le N$)
• $1 \le L_j \le R_j \le N$ ($1 \le j \le Q$)
• $-1\,000\,000 \le X_j \le 1\,000\,000$ ($1 \le j \le Q$)
• All input values are integers.