Fair Haybale Distribution

Farmer John wants to distribute a sequence of haybales fairly between his two favorite cows, Bessie and Elsie. He has N haybales, sorted in descending order, where the i-th haybale has a_i units of hay. The haybale amounts satisfy \(2\cdot10^5 \ge a_1 \ge a_2 \ge \cdots \ge a_N \ge 1\).

He plans to choose a continuous segment of haybales \(a_l, a_{l+1}, \dots, a_r\) and distribute them one by one in order. When processing a haybale, he gives it to the cow which currently has less total hay. In the case of a tie, Bessie receives the haybale.

You are given an initial difference \(x\) representing that Bessie initially has \(x\) more units of hay than Elsie. (Note: \(|x|\) can be up to \(10^9\).) For each query consisting of three integers \(l, r, x\), determine the final difference in hay between Bessie and Elsie (Bessie's hay minus Elsie's hay) after distributing haybales from index \(l\) to \(r\). If Elsie ends up with more hay, output a negative number.

Decision rule: For each haybale with value \(a\), if the current difference \(d \le 0\) then assign the haybale to Bessie (so \(d\) becomes \(d + a\)); otherwise, assign it to Elsie (so \(d\) becomes \(d - a\)).

Constraints:

• \(1 \le N \le 2\cdot10^5\)
• \(1 \le Q \le 2\cdot10^5\)
• \(1 \le l \le r \le N\)
• \(|x| \le 10^9\)

inputFormat

The first line contains two integers N and Q separated by a space.

The second line contains N integers \(a_1, a_2, \dots, a_N\) in descending order.

Then Q lines follow. Each line contains three integers l, r, and x, representing a query.

outputFormat

For each query, output a single integer: the final difference in hay (Bessie's total minus Elsie's total) after the haybales in the segment are distributed.

sample

5 3
10 5 3 2 1
1 3 0
2 5 5
1 5 -5

2
0
0