Вася изобрел новую хеш-функцию для массива. Она считается следующим образом. Пока в массиве есть хотя бы два числа, нужно удалить из массива два первых числа, пусть это $$$a_1$$$ и $$$a_2$$$, и добавить в начало число $$$a_2 - a_1$$$. Как только массив будет состоять всего из одного числа, это число и будет значением хеш-функции Васи этого массива.
У Васи есть массив $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$. Он выполняет над ним $$$q$$$ операций вида «увеличить все элементы на отрезке $$$[l_j, r_j]$$$ на величину $$$v_j$$$». После каждой операции он хочет знать, чему стала равна хеш-функция Васи этого массива.
В первой строке записано целое число $$$n$$$ ($$$1 \le n \le 500000$$$) — размер массива.
Во второй строке записано $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива.
В третьей строке записано целое число $$$q$$$ ($$$1 \le q \le 200000$$$) — количество операций.
В каждой из следующих $$$q$$$ строк записано три целых числа $$$l_j$$$, $$$r_j$$$, $$$v_j$$$ ($$$1 \le l_j \le r_j \le n,~-10^9 \le v_j \le 10^9$$$) — параметры $$$j$$$-й операции.
Выведите $$$q$$$ строк. В $$$j$$$-й строке выведите целое число — значение хеш-функции Васи после $$$j$$$-й операции.
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
