Codeforces Round 905 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

brute force

constructive algorithms

data structures

greedy

hashing

two pointers

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Minimum Array

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Example

Input

241 2 3 421 4 01 3 -10052 1 2 5 432 4 32 5 -21 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$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 09:29:05 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|