在 IOI 王国，风总是从海洋吹向陆地。这里有 $N+1$ 个地点，编号从 $0$ 到 $N$。风从地点 $0$ 吹向地点 $N$。JOI 先生在地点 $N$ 有一栋房子。地点 $0$ 的海拔为 $A_0 = 0$，地点 $i$ ($1 \le i \le N$) 的海拔为 $A_i$。

风在地表吹拂。风的温度会随着海拔的变化而改变。最靠近海洋的地点 $0$ 的风温为 $0$ 度。对于每个 $i$ ($0 \le i \le N-1$)，从地点 $i$ 到地点 $i+1$ 的风温变化仅取决于 $A_i$ 和 $A_{i+1}$ 的值，具体规则如下：

• 如果 $A_i < A_{i+1}$，风温每单位海拔降低 $S$ 度。
• 如果 $A_i \ge A_{i+1}$，风温每单位海拔升高 $T$ 度。

IOI 王国的地壳运动非常活跃。你有 $Q$ 天的地壳运动数据。在第 $j$ 天 ($1 \le j \le Q$)，地点 $k$ ($L_j \le k \le R_j$, $1 \le L_j \le R_j \le N$) 的海拔变化量为 $X_j$。如果 $X_j$ 非负，则海拔增加 $X_j$；如果 $X_j$ 为负，则海拔减少 $|X_j|$。

你的任务是计算在每次地壳运动后，JOI 先生房子处的风温。

任务

给定地壳运动数据，编写一个程序，计算在第 $j$ 天 ($1 \le j \le Q$) 的地壳运动后，JOI 先生房子处的风温。

输入格式

从标准输入读取以下数据：

• 第一行包含四个空格分隔的整数 $N, Q, S, T$。这表示 JOI 先生的房子位于地点 $N$，共有 $Q$ 次地壳运动，若海拔升高，风温每单位海拔降低 $S$ 度，若海拔降低，风温每单位海拔升高 $T$ 度。
• 接下来的 $N+1$ 行中的第 $i$ 行 ($1 \le i \le N+1$) 包含一个整数 $A_{i-1}$，表示地壳运动前地点 $i-1$ 的初始海拔。
• 接下来的 $Q$ 行中的第 $j$ 行 ($1 \le j \le Q$) 包含三个空格分隔的整数 $L_j, R_j, X_j$。这表示第 $j$ 天的地壳运动中，地点 $L_j$ 到 $R_j$ 的海拔变化量为 $X_j$。

输出格式

输出 $Q$ 行到标准输出。第 $j$ 行 ($1 \le j \le Q$) 包含第 $j$ 天地壳运动后 JOI 先生房子处的风温。

数据范围

所有输入数据满足以下条件：

• $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$)

子任务

子任务 1 [30 分]

满足以下条件： $N \le 2\,000$ $Q \le 2\,000$

子任务 2 [10 分]

• $S = T$

子任务 3 [60 分]

无附加限制。

样例

样例输入 1

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

样例输出 1

-5
-7
-13
-13
-18

说明

最初，地点 $0, 1, 2, 3$ 的海拔分别为 $0, 4, 1, 8$。第一天地壳运动后，海拔变为 $0, 6, 3, 8$。此时，风温分别为 $0, -6, 0, -5$。

样例输入 2

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

样例输出 2

5
-35

说明

此样例输入满足子任务 2 的限制。

样例输入 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

样例输出 3

277
277
322
290
290
290
290
370