Ở Vương quốc IOI, gió luôn thổi từ biển vào đất liền. Có \(N+1\) địa điểm được đánh số từ \(0\) đến \(N\) theo hướng gió thổi. Nhà của ông JOI nằm tại địa điểm \(N\). Độ cao của địa điểm \(0\) là \(A_0=0\), còn độ cao của địa điểm \(i\) là \(A_i\).

Gió chuyển động sát mặt đất. Nhiệt độ gió tại địa điểm \(0\), nơi gần biển nhất, là \(0\) độ. Với mỗi \(0\le i<N\), nhiệt độ thay đổi từ địa điểm \(i\) đến địa điểm \(i+1\) như sau:

• Nếu \(A_i<A_{i+1}\), nhiệt độ giảm \(S\) độ trên mỗi đơn vị độ cao tăng lên.
• Nếu \(A_i\ge A_{i+1}\), nhiệt độ tăng \(T\) độ trên mỗi đơn vị độ cao giảm xuống.

Hoạt động kiến tạo ở Vương quốc IOI rất mạnh. Bạn có dữ liệu về chuyển động kiến tạo trong \(Q\) ngày. Vào ngày thứ \(j\), độ cao của mọi địa điểm \(k\) với \(L_j\le k\le R_j\) thay đổi thêm \(X_j\). Nếu \(X_j\ge 0\), độ cao tăng \(X_j\); nếu \(X_j<0\), độ cao giảm \(|X_j|\).

Hãy tính nhiệt độ gió tại nhà ông JOI sau chuyển động kiến tạo của từng ngày.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên \(N,Q,S,T\).
• \(N+1\) dòng tiếp theo lần lượt chứa \(A_0,A_1,\ldots,A_N\); mỗi số nằm trên một dòng.
• \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(L_j,R_j,X_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa nhiệt độ gió tại nhà ông JOI sau chuyển động kiến tạo ngày thứ \(j\).

Ràng buộc

• \(1\le N,Q\le 200\,000\).
• \(1\le S,T\le 1\,000\,000\).
• \(A_0=0\).
• \(-1\,000\,000\le A_i\le 1\,000\,000\) với \(1\le i\le N\).
• \(1\le L_j\le R_j\le N\).
• \(-1\,000\,000\le X_j\le 1\,000\,000\).

Phân nhóm

1. \(30\) điểm: \(N\le 2\,000\) và \(Q\le 2\,000\)
2. \(10\) điểm: \(S=T\)
3. \(60\) điểm: Không có ràng buộc bổ sung

Ví dụ

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

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

5
-35

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

277
277
322
290
290
290
290
370

Nguồn

JOI 2016/2017, Vòng chung kết.