C. Минимальный массив
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$, состоящий из целых чисел. Далее к нему последовательно $$$q$$$ раз применяют следующую операцию:

  • Выбирают индексы $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) и целое число $$$x$$$;
  • Ко всем элементам массива $$$a$$$ на отрезке $$$[l, r]$$$ прибавляют $$$x$$$. Более формально, присваивают $$$a_i := a_i + x$$$ для всех $$$l \le i \le r$$$.

Пусть $$$b_j$$$ — массив $$$a$$$, полученный после применения первых $$$j$$$ операций ($$$0 \le j \le q$$$). Обратите внимание, что $$$b_0$$$ — это массив $$$a$$$ до применения всех операций.

Вам нужно найти лексикографически минимальный$$$^{\dagger}$$$ массив среди всех $$$b_j$$$.

$$$^{\dagger}$$$Массив $$$x$$$ лексикографически меньше чем массив $$$y$$$, если есть индекс $$$i$$$ такой, что $$$x_i < y_i$$$, и $$$x_j = y_j$$$ для всех $$$j < i$$$. Иными словами, для первого такого индекса $$$i$$$, где массивы различны, $$$x_i < y_i$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Третья строка каждого набора входных данных содержит одно целое число $$$q$$$ ($$$0 \le q \le 5 \cdot 10^5$$$) — количество операций с массивом.

В каждой из следующих $$$q$$$ строк находятся по три целых числа $$$l_j$$$, $$$r_j$$$ и $$$x_j$$$ $$$(1 \le l_j \le r_j \le n, -10^9 \le x_j \le 10^9)$$$ — описание каждой операции. Операции следуют в порядке их применения.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите лексикографически минимальный массив среди всех $$$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
Примечание

В первом наборе входных данных:

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

Таким образом, лексикографически минимальным является массив $$$b_2$$$.

Во втором наборе входных данных лексикографически минимальным является массив $$$b_0$$$.