310784: CF1887C. Minimum Array

C. Minimum Arraytime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

ExampleInput

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

Output

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

题目大意：
给定一个由整数组成的长度为n的数组a。然后按顺序对它应用以下操作q次：
1. 选择索引l和r（1≤l≤r≤n）和一个整数x；
2. 将x加到数组a中在区间[l, r]内的所有元素上。更正式地说，对所有l≤i≤r，赋值a_i:=a_i+x。
令b_j是在应用前j个操作后得到的数组a（0≤j≤q）。注意b_0是在应用任何操作之前的数组a。
你需要找到所有数组b_j中字典序最小的数组。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤5×10^5）——测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数n（1≤n≤5×10^5）——数组a的长度。
每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（-10^9≤a_i≤10^9）——数组a的元素。
每个测试用例的第三行包含一个整数q（0≤q≤5×10^5）——对数组进行的操作数量。
在接下来的q行中，每行有三个整数l_j, r_j, 和x_j（1≤l_j≤r_j≤n, -10^9≤x_j≤10^9）——每个操作的描述。操作按应用的顺序给出。
保证所有测试用例的n之和和所有测试用例的q之和不超过5×10^5。

输出数据格式：
对于每个测试用例，输出所有数组b_j中字典序最小的数组。题目大意： 给定一个由整数组成的长度为n的数组a。然后按顺序对它应用以下操作q次： 1. 选择索引l和r（1≤l≤r≤n）和一个整数x； 2. 将x加到数组a中在区间[l, r]内的所有元素上。更正式地说，对所有l≤i≤r，赋值a_i:=a_i+x。 令b_j是在应用前j个操作后得到的数组a（0≤j≤q）。注意b_0是在应用任何操作之前的数组a。 你需要找到所有数组b_j中字典序最小的数组。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤5×10^5）——测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含一个整数n（1≤n≤5×10^5）——数组a的长度。 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（-10^9≤a_i≤10^9）——数组a的元素。 每个测试用例的第三行包含一个整数q（0≤q≤5×10^5）——对数组进行的操作数量。 在接下来的q行中，每行有三个整数l_j, r_j, 和x_j（1≤l_j≤r_j≤n, -10^9≤x_j≤10^9）——每个操作的描述。操作按应用的顺序给出。 保证所有测试用例的n之和和所有测试用例的q之和不超过5×10^5。 输出数据格式： 对于每个测试用例，输出所有数组b_j中字典序最小的数组。