Minimum Array
Description
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$.
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$.
For each test case, output the lexicographically minimum array among all arrays $b_j$.
Input
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
For each test case, output the lexicographically minimum array among all arrays $b_j$.
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
-99 -98 -97 4
2 1 2 5 4
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$.