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 \lt y_i$$$, and $$$x_j = y_j$$$ for all $$$j \lt i$$$. In other words, for the first index $$$i$$$ where the arrays differ, $$$x_i \lt y_i$$$.

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$$$.

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$$$.

Minimum Array

Examples