There are $n$ mountains, and the height of the $i$-th mountain is $a_i$. Marisa will start climbing from the base of mountain $0$ and will successively pass through the peaks of mountains $1, 2, \dots, n$.
Marisa's stamina starts at $0$. When moving from position $i$ to position $i+1$, there are two possible scenarios:
- If $a_i < a_{i + 1}$: Marisa's stamina decreases by $S \times |a_i - a_{i + 1}|$.
- If $a_i \ge a_{i + 1}$: Marisa's stamina increases by $T \times |a_i - a_{i + 1}|$.
On each day $i$ in the next $q$ days, due to tectonic movements, the heights of all the mountains in the range $[l_i, r_i]$ will change by $x_i$. Help Marisa calculate her stamina after climbing over all $n$ mountains each day. Note that the stamina can be negative.
### Input
- The first line contains four integers $n, q, S, T$.
- The next $n + 1$ lines, where the $i$-th line contains the height of position $i-1$.
- The next $q$ lines, where the $i$-th line contains three integers $l_i, r_i, x_i$.
### Output
- For each day, print Marisa's stamina after she has climbed over all $n$ mountains.
### Constraints
- $1 \le n, q \le 2 \times 10^5$.
- $1 \le S, T \le 10^6$.
- $a_0 = 0, |a_i| \le 10^6 \forall 1 \le i \le n$.
- $1 \le l_i \le r_i \le n$.
- $|x_i| \le 10^6$.
### 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
```
