406836: GYM102569 A Array's Hash

Vasya has invented a new hash function of an array. It is calculated as follows. While the array has at least two elements, the first two elements, call them $$$a_1$$$ and $$$a_2$$$, are deleted, and the new element $$$a_2 - a_1$$$ is inserted to the beginning of the array. When the array has only one element, this number is a value of Vasya's hash function of this array.

Vasya has the array $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$. He performs $$$q$$$ operations of the following form: "increase all elements in the segment $$$[l_j, r_j]$$$ by $$$v_j$$$". After each operation he wants to know the value of Vasya's hash function of this array.

The first line contains an integer $$$n$$$ ($$$1 \le n \le 500000$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of the array.

The third line contains an integer $$$q$$$ ($$$1 \le q \le 200000$$$) — the number of operations.

Each of the next $$$q$$$ lines contains three integers $$$l_j$$$, $$$r_j$$$, $$$v_j$$$ ($$$1 \le l_j \le r_j \le n,~-10^9 \le v_j \le 10^9$$$) — the parameters of the $$$j$$$-th operation.

Output $$$q$$$ lines. In the $$$j$$$-th line output one integer — the value of Vasya's hash function after the $$$j$$$-th operation.

7
4 2 -5 10 4 -2 6
4
2 4 -8
5 7 2
3 3 -1
3 7 3

7
9
8
11