配点: 100 点
在IOI国家,风总是从海上吹向陆地。风是一个点 0 点 经过路线 1,地点 2,\ldots 时的点 吹直到 N 。点 JOI 的房子正在 N 建造。点 0 的海拔高度是 A_0 = 0 以及要点 i (1 \leqq i \leqq N) 的海拔高度是 A_i 。
风沿着地表吹,风的温度随着海拔的变化而变化。触及大海的点 0 处的风温为 0 度,以及所有 i (0 \leqq i \leqq N - 1),重点 i 点 经过路线 i + 1 期间风温的变化为 它仅取决于 A_i 和 A_{i + 1} ,如下所示。
- A_i < A_{i + 1} 时,海拔高度为 1 随着风温升高, S 它下降了。
- A_i \geqq A_{i + 1} 时,海拔高度为 1 随着风的温度降低, T 程度增加。
IOI国境内地壳运动活跃。你是Q 我们获得了每日地壳变形数据。j 日目 (1 \leqq j \leqq Q)中有L_j \leqq k \leqq R_j (1 \leqq L_j \leqq R_j \leqq N) 满足点的高程 由 A_k 是 X_j 更改。 当X_j 非负时,海拔高度为 这意味着它增加了 X_j , 当X_j 为负数时,海拔高度为 这意味着它将减少 |X_j| 。
你的工作是找出每次地壳变形发生后 JOI 家吹来的风的温度。
課題
给出地壳变形前的高程和地壳变形信息时,全部为整数 j (1 \leqq j \leqq Q),j 第一天发生地壳变形后的 JOI。编写一个程序来查找吹到你家的风的温度。
入力
从标准输入读取以下输入。 在
- 1 行中, 4 整数 给出 N, Q, S, T 以空格作为分隔符。这些点都是JOI的家。 建于 N ,构造运动次数为 Q 海拔高度是 1 风的温度随着上升而升高。 S 程度降低,1 每次下降 T 代表程度的增加。
- 继续 N + 1 行 i 行目 (1 \leqq i \leqq N + 1) 是重点 一个整数,表示 i - 1 处地壳变形前的高程 写入 A_{i - 1} 。
- 继续 Q 行 j 行目 (1 \leqq j \leqq Q)中有3 整数 给出 L_j, R_j, X_j 以空格作为分隔符。这些是j 当日地壳变形点 海拔高度可达 L_j 到 R_j 代表 X_j 的更改。
出力
输出是 由 Q 行组成。标准输出 j 行目 (1 \leqq j \leqq Q)中有j 第一天发生地壳变形后的 JOI。输出吹到你家的风的温度。
制限
所有输入数据满足以下条件。
- 1 \leqq N \leqq 200\,000.
- 1 \leqq Q \leqq 200\,000.
- 1 \leqq S \leqq 1\,000\,000.
- 1 \leqq T \leqq 1\,000\,000.
- A_0 = 0.
- -1\,000\,000 \leqq A_i \leqq 1\,000\,000 (1 \leqq i \leqq N).
- 1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q).
- -1\,000\,000 \leqq X_j \leqq 1\,000\,000 (1 \leqq j \leqq Q).
小課題
小課題 1 [30 点]
满足以下条件。
- N \leqq 2\,000.
- Q \leqq 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 。1 当日地壳形变后,高程分别为 0, 6, 3, 8变为。此时,重点是 0, 1, 2, 3 处的风温为 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