푄 현상

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}$이면 고도 1당 바람의 온도가 $S$도씩 내려간다. 즉 온도가 $S \times (A_{i+1} - A_i)$도 내려간다.
• $A_i \ge A_{i+1}$이면 고도 1당 바람의 온도가 $T$도씩 올라간다. 즉 온도가 $T \times (A_i - A_{i+1})$도 올라간다.

IOI 왕국의 땅에서는 지각 변동이 활발하다. $Q$일 동안의 지각 변동 기록이 주어진다. $j$일째($1 \le j \le Q$)에는 $L_j \le k \le R_j$인 모든 $k$번 지점의 고도가 $X_j$만큼 변한다($1 \le L_j \le R_j \le N$). $X_j$가 음이 아니면 고도가 $X_j$만큼 올라가고, $X_j$가 음수이면 고도가 $|X_j|$만큼 내려간다. 각 지각 변동은 그 전날까지 바뀐 고도에 이어서 적용된다.

지각 변동 기록이 주어질 때, 각 $j$($1 \le j \le Q$)에 대해 $j$일째 지각 변동 직후 JOI 씨의 집에서 바람의 온도를 구하는 프로그램을 작성하시오.

첫째 줄에 네 정수 $N$, $Q$, $S$, $T$가 공백으로 구분되어 주어진다. JOI 씨의 집은 $N$번 지점에 있고, 지각 변동은 $Q$번 일어난다. 고도가 올라가면 고도 1당 바람의 온도가 $S$도 내려가고, 고도가 내려가면 고도 1당 바람의 온도가 $T$도 올라간다.

다음 $N + 1$개의 줄 중 $i$번째 줄($1 \le i \le N + 1$)에는 지각 변동 전 $(i - 1)$번 지점의 고도인 정수 $A_{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$)
• 입력으로 주어지는 모든 값은 정수이다.