题目描述

IOI 国的风一直从海上向陆地方向吹。沿风向依次有 $0,1,2,\ldots,n$ 共 $n+1$ 个地点，其中地点 $0$ 的海拔高度为 $a_0=0$，地点 $i$ 的海拔高度为 $a_i$。

风沿地表吹过时，温度会随高度变化。地点 $0$ 的风温为 $0$ 度。对于所有 $i$（$0\le i\lt n$），风从地点 $i$ 到达地点 $i+1$ 时：

• 若 $a_i\lt 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$ 天，区间 $[L_j,R_j]$ 内所有地点的海拔高度都增加 $x_j$。当 $x_j\lt 0$ 时，表示这些地点的海拔高度下降 $|x_j|$。

请在每天的地壳变动结束后，输出地点 $n$ 的风温。

输入格式

第一行包含四个整数 $n,Q,S,T$。

接下来 $n+1$ 行，第 $i+1$ 行包含一个整数 $a_i$，表示地点 $i$ 的海拔高度。

接下来 $Q$ 行，第 $j$ 行包含三个整数 $L_j,R_j,x_j$，表示第 $j$ 天的地壳变动。

输出格式

输出 $Q$ 行，每行一个整数。第 $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

数据范围

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

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

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

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