该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有一天，HakuroKawashiro（以下简称HK）上完地理课后，想到了一个问题。

HK的家距离东海岸有 $n$ 千米，我们把东海岸的位置标记为 $0$ ，把HK家标记为 $n$ ，中间有 $n - 1$ 个点从 $1$ 至 $n - 1$ ，每隔1千米依次标记。一开始 $0$ 处的海拔高度永远为0，对于第 $i$ 处标记，其海拔高度为 $a_i$ 米。有一阵风会从东海岸开始直线吹向HK家，并且风的初始温度为0度。根据地理学相关知识，风的温度会随海拔的变化而变化。变化规则如下：

• 若 a_i $\lt$ a_i+1 ,则风每升高1米就要下降 $s$ 度。
• 若 a_i $\ge$ a_i+1 ,则风每下降1米就要升高 $t$ 度。

由于当地的地壳运动变化非常活跃，几乎每天都有部分地方发生地壳变化。在接下来的 $q$ 天，对于第 $j$ 天，从标记 $l_j$ 至标记 $r_j$ 处这段区间的海拔高度会变化 $x_j$ 米。

HK想知道的是，在接下来的 $q$ 天内，每天风吹到HK家时的温度为多少？

Input Format

第一行4个整数 $n , q , s , t$ 。

第二行 $n$ 个整数，对于第 $i$ 个整数 $a_i$ ，代表第 $i$ 处的海拔高度。

接下来的 $q$ 行，对于第 $j$ 行，有3个数 $l_j , r_j , x_j$ 。

相关变量的意义见题目描述。

Output Format

输出 $q$ 行，对于第 $j$ 行的数，表示第 $j$ 天风吹到HK家时的温度。

Sample

【样例1输入】

3 5 1 2
4 1 8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5

【样例1输出】

-5
-7
-13
-13
-18

【样例1解释】

地壳未变化时，风吹至HK家时的温度为-5度。

第1天，海拔变化为 6 3 8 ，风吹至HK家时的温度为-5度。

第2天，海拔变化为 4 3 8 ，风吹至HK家时的温度为-7度。

第3天，海拔变化为4 8 13 ，风吹至HK家时的温度为-13度。

第4天，海拔变化为 3 7 13 ，风吹至HK家时的温度为-13度。

第5天，海拔变化为 8 12 18 ，风吹至HK家时的温度为-18度。

【样例2输入】

2 2 5 5
6 -1
1 1 4
1 2 8

【样例2输出】

5
-35

【样例3输入】

7 8 8 13
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

【样例3输出】

277
277
322
290
290
290
290
370

Hint

对于 $20 \%$ 的数据，有 $1 \leq n , q \leq 500$ 。

对于另外的 $20 \%$ 的数据，有 $s = t$ ，且一个标记的地壳变化最多只发生一次。

对于 $100 \%$ 的数据，有

• $1 \leq n \leq 200000$
• $1 \leq q \leq 200000$
• $1 \leq s ,t \leq 10 ^ 6$
• $| a_i | \leq 10 ^ 6 ( 1 \leq i \leq n )$
• $1 \leq l_j \leq r_j \leq n( 1 \leq j \leq q)$
• $| x_i | \leq 10 ^ 6 ( 1 \leq j \leq q )$