题目描述

IOI 国的风一直是从海上向陆地方向吹的。风从地点 $0$ 开始，按顺序吹过地点 $1,2,\ldots,n$。地点 $0$ 的海拔高度 $a_0=0$，地点 $i$ 的海拔高度是 $a_i$。

风沿着地表吹过时，温度会随着高度变化而变化。在地点 $i$ 的风的温度是 $0$ 度，对于所有的 $i$（$0\le i\le n-1$），从地点 $i$ 到地点 $i+1$ 时，风的温度变化如下：

• 如果 $a_i<a_{i+1}$，风的温度下降 $(a_{i+1}-a_i)\times S$ 度。
• 如果 $a_i\ge a_{i+1}$，风的温度上升 $(a_i-a_{i+1})\times T$ 度。

IOI 国的地壳变动很剧烈，你知道了最近 $Q$ 天每天的地壳变动信息。第 $j$ 天（$1\le j\le Q$），地点 $L_j\sim R_j$（包括端点）的海拔高度会变化 $x_j$。如果 $x_j$ 非负表示上升 $x_j$，如果 $x_j$ 是负数表示下降 $|x_j|$。

你的任务是在每天的地壳变动后，输出地点 $n$ 处的风的温度。

输入格式

第 $1$ 行，$4$ 个整数 $n,Q,S,T$。

接下来 $n+1$ 行，每行 $1$ 个整数 $a_i$，分别表示地点 $0,1,2,\ldots,n$ 的海拔高度。

接下来 $Q$ 行，每行 $3$ 个整数 $L_j,R_j,x_j$，表示第 $j$ 天的地壳变动信息。

输出格式

输出 $Q$ 行，每行 $1$ 个整数，第 $j$ 行表示第 $j$ 天地壳变动后，地点 $n$ 的风的温度。

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

-5
-7
-13
-13
-18

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

-9
-21

2 2 2 1
0
3
1
1 2 1
2 2 -3

-6
-3

样例说明

最初，地点 $0,1,2,3$ 的海拔分别是 $0,4,1,8$。

第 $1$ 天地壳变动后，海拔变成 $0,6,3,8$；此时地点 $0,1,2,3$ 的风的温度分别是 $0,-6,0,-5$。

第 $2$ 天后海拔变成 $0,4,3,8$，第 $3$ 天后变成 $0,4,8,13$，第 $4$ 天后变成 $0,3,7,13$，第 $5$ 天后变成 $0,8,12,18$。

数据范围与约定

• 对于 $30\%$ 的数据：$n,Q\le2000$；
• 另有 $10\%$ 的数据：$S=T$；
• 对于 $100\%$ 的数据：$1\le n,Q\le2\times10^5$，$1\le S,T\le10^6$，$a_0=0$，$-10^6\le a_i\le10^6$（$1\le i\le n$），$1\le L_j\le R_j\le n$，$-10^6\le x_j\le10^6$（$1\le j\le Q$）。