14419번 - Foehn Phenomena 서브태스크다국어

In the Kingdom of IOI, the wind always blows from sea to land. There are N + 1 spots numbered from 0 to N. The wind from Spot 0 to Spot N in order. Mr. JOI has a house at Spot N. The altitude of Spot 0 is A₀ = 0, and the altitude of Spot i (1 ≤  i ≤ N) is A_i.

The wind blows on the surface of the ground. The temperature of the wind changes according to the change of the altitude. The temperature of the wind at Spot 0, which is closest to the sea, is 0 degree. For each i (0 ≤  i ≤ N - 1), the change of the temperature of the wind from Spot i to Spot i + 1 depends only on the values of A_i and A_i+1 in the following way:

• If A_i < A_i+1, the temperature of the wind decreases by S degrees per altitude.
• If A_i ≧ A_i+1, the temperature of the wind increases by T degrees per altitude.

The tectonic movement is active in the land of the Kingdom of IOI. You have the data of tectonic movements for Q days. In the j-th (1 ≤  j ≤ Q) day, the change of the altitude of Spot k for L_j ≤ k ≤ R_j (1 ≤ L_j ≤ R_j ≤ N) is described by X_j. If X_j is not negative, the altitude increases by X_j. If X_j is negative, the altitude decreases by |X_j|.

Your task is to calculate the temperature of the wind at the house of Mr. JOI after each tectonic movement.

Given the data of tectonic movements, write a program which calculates, for each j (1 ≤ j ≤ Q), the temperature of the wind at the house of Mr. JOI after the tectonic movement on the j-th day.

Read the following data from the standard input.

• The first line of input contains four space separated integers N; Q; S; T. This means there is a house of Mr. JOI at Spot N, there are Q tectonic movements, the temperature of the wind decreases by S degrees per altitude if the altitude increases, and the temperature of the wind increases by T degrees per altitude if the altitude decreases.
• The i-th line (1 ≤ i ≤ N +1) of the following N +1 lines contains an integer A_i-1, which is the initial altitude at Spot (i - 1) before tectonic movements.
• The j-th line (1 ≤ j ≤ Q) of the following Q lines contains three space separated integers L_j; R_j; X_j. This means, for the tectonic movement on the j-th day, the change of the altitude at the spots from L_j to R_j is described by X_j.

Write Q lines to the standard output. The j-th line (1 ≤ j ≤ Q) of output contains the temperature of the wind at the house of Mr. JOI after the tectonic movement on the j-th day.

All input data satisfy the following conditions.

• 1 ≤ N ≤ 200 000.
• 1 ≤ Q ≤ 200 000.
• 1 ≤ S ≤ 1 000 000.
• 1 ≤ T ≤ 1 000 000.
• A₀ = 0.
• -1 000 000 ≤ A_i ≤ 1 000 000 (1 ≤ i ≤ N).
• 1 ≤ L_j ≤ R_j ≤ N (1 ≤ j ≤ Q).
• -1 000 000 ≤ X_j ≤ 1 000 000 (1 ≤ j ≤ Q).