Minimum Array
Contest: Codeforces Round 905 (Div. 1)
Difficulty rating: 2400
Tags: binary search, brute force, constructive algorithms, data structures, greedy, hashing, two pointers

Given an array $$$a$$$ of length $$$n$$$ consisting of integers. Then the following operation is sequentially applied to it $$$q$$$ times:

- Choose indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) and an integer $$$x$$$;
- Add $$$x$$$ to all elements of the array $$$a$$$ in the segment $$$[l, r]$$$. More formally, assign $$$a_i := a_i + x$$$ for all $$$l \le i \le r$$$.

Let $$$b_j$$$ be the array $$$a$$$ obtained after applying the first $$$j$$$ operations ($$$0 \le j \le q$$$). Note that $$$b_0$$$ is the array $$$a$$$ before applying any operations.

You need to find the lexicographically minimum$$$^{\dagger}$$$ array among all arrays $$$b_j$$$.

$$$^{\dagger}$$$An array $$$x$$$ is lexicographically smaller than array $$$y$$$ if there is an index $$$i$$$ such that $$$x_i < y_i$$$, and $$$x_j = y_j$$$ for all $$$j < i$$$. In other words, for the first index $$$i$$$ where the arrays differ, $$$x_i < y_i$$$.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.

The third line of each test case contains a single integer $$$q$$$ ($$$0 \le q \le 5 \cdot 10^5$$$) — the number of operations on the array.

In each of the next $$$q$$$ lines, there are three integers $$$l_j$$$, $$$r_j$$$, and $$$x_j$$$ $$$(1 \le l_j \le r_j \le n, -10^9 \le x_j \le 10^9)$$$ — the description of each operation. The operations are given in the order they are applied.

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$q$$$ over all test cases do not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, output the lexicographically minimum array among all arrays $$$b_j$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

- $$$b_0 = [1,2,3,4]$$$;
- $$$b_1 = [1,2,3,4]$$$;
- $$$b_2 = [-99,-98,-97,4]$$$.

Thus, the lexicographically minimum array is $$$b_2$$$.

In the second test case, the lexicographically minimum array is $$$b_0$$$.

Example input:
2
4
1 2 3 4
2
1 4 0
1 3 -100
5
2 1 2 5 4
3
2 4 3
2 5 -2
1 3 1

Example output:
-99 -98 -97 4 
2 1 2 5 4

Editorial:
Let $$$u$$$ be a difference array of an array $$$v$$$, i.e. $$$u_0 = v_0$$$, $$$u_i = v_i - v_{i-1}$$$ for all $$$i \ge 1$$$.
Note that minimizing an array is equivalent to minimizing its difference array. Let's see how the difference array changes: when asked, adding the number $$$add$$$ on the segment $$$[l; r]$$$ only 2 elements are updated in it: $$$add$$$ is added to the $$$l$$$th index, and $$$add$$$ is subtracted from the $$$r+1$$$th index.
Let's learn how to compare difference arrays after the $$$j$$$th and $$$i$$$th queries ($$$j < i$$$). Let's consider an auxiliary array, which is a union of changes in the difference array for all queries with numbers from $$$j+1$$$ to $$$i$$$ inclusive. Consider in this auxiliary array the minimum non-zero element by index. Note that if it is negative, then the difference array after the $$$i$$$th query will be smaller than after the $$$j$$$th one, and if it is positive, then it will be larger.
Let's go through the queries and maintain the number of the minimum difference array. Let the current minimum difference array after request be number $$$j$$$. Since changes to the difference array occur only in two indexes, we can maintain them in a dictionary containing changes to the difference array by index. When we want to process the next request, we update the values in the dictionary using two keys. After the change, you need to check the sign of the minimum non-zero element by index:
1. If it is negative, then this means that the current request has updated the minimum, and we clear the dictionary so that we can now store changes relative to this request in it.
2. If it is positive, then we leave the dictionary the same and continue to change it in subsequent queries.
As a result, using the found index of the minimum difference array, we restore the array itself.