CF1406D Three Sequences

You are given a sequence of $ n $ integers $ a_1, a_2, \ldots, a_n $ . You have to construct two sequences of integers $ b $ and $ c $ with length $ n $ that satisfy: - for every $ i $ ( $ 1\leq i\leq n $ ) $ b_i+c_i=a_i $ - $ b $ is non-decreasing, which means that for every $ 1

The first line contains an integer $ n $ ( $ 1\leq n\leq 10^5 $ ). The secound line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\leq i\leq n $ , $ -10^9\leq a_i\leq 10^9 $ ). The third line contains an integer $ q $ ( $ 1\leq q\leq 10^5 $ ). Each of the next $ q $ lines contains three integers $ l,r,x $ ( $ 1\leq l\leq r\leq n,-10^9\leq x\leq 10^9 $ ), desribing the next change.

Print $ q+1 $ lines. On the $ i $ -th ( $ 1 \leq i \leq q+1 $ ) line, print the answer to the problem for the sequence after $ i-1 $ changes.

In the first test: - The initial sequence $ a = (2, -1, 7, 3) $ . Two sequences $ b=(-3,-3,5,5),c=(5,2,2,-2) $ is a possible choice. - After the first change $ a = (2, -4, 4, 0) $ . Two sequences $ b=(-3,-3,5,5),c=(5,-1,-1,-5) $ is a possible choice. - After the second change $ a = (2, -4, 6, 2) $ . Two sequences $ b=(-4,-4,6,6),c=(6,0,0,-4) $ is a possible choice.