Большие вызовы

На проектной смене в образовательном центре <<Сириус>> участники одной из команд проектируют промышленных роботов.

Роботы будут наполнять деталями $n$ контейнеров, которые стоят в ряд и пронумерованы от $1$ до $n$. В $i$-й контейнер можно суммарно поместить не больше $a\_i$ деталей. Участники собрали $m$ роботов. Изначально у $j$-го робота имеется $c\_j$ деталей, часть из которых он положит в контейнеры. Также, у $j$-го робота есть диапазон действия, задающийся двумя числами $l\_j \le r\_j$, означающий, что робот может класть детали только в контейнеры с номерами от $l\_j$ до $r\_j$ включительно. Роботы пытаются суммарно положить в контейнеры как можно больше деталей.

Созданные роботы бывают двух типов. Если тип робота $t\_j = 0$, то его диапазон действия всегда остается неизменным. А роботов типа $t\_j = 1$ можно перепрограммировать. Если контейнер с номером $x$ выделить как наиболее важный, диапазон действия каждого робота типа $1$ расширяется минимальным образом, чтобы он стал содержать контейнер $x$. Более формально, диапазон действия робота номер $j$, имеющего тип $1$, изменяется на $\[\min(l\_j, x), \max(r\_j, x)]$.

Для каждого $x$ от $1$ до $n$ вычислите, какое максимальное количество деталей роботы смогут суммарно поместить в контейнеры, если важным будет контейнер с номером $x$, а роботы будут действовать оптимальным образом.

Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число $t$ ($1 \leq t \leq 200\\,000$) --- количество наборов входных данных. Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных даны два целых числа $n$ и $m$ ($1 \le n, m \le 200\\,000$) --- количество контейнеров и роботов соответственно.

В следующей строке даны $n$ целых чисел $a\_i$ ($0 \le a\_i \le 10^9$) --- вместимости контейнеров.

В каждой из следующих $m$ строк даны по четыре целых числа $l\_j$, $r\_j$, $c\_j$, $t\_j$ ($1 \le l\_j \le r\_j \le n$, $0 \le c\_j \le 10^9$, $t\_j \in \\{0, 1\\}$) --- диапазон действия, изначальное количество деталей и тип робота соответственно.

Обозначим за $\sum n$ сумму $n$, а за $\sum m$ сумму $m$ по всем наборам входных данных в одном тесте. Гарантируется, что $\sum n \leq 200\\,000$, $\sum m \leq 200\\,000$.

Для каждого набора входных данных выведите $n$ целых чисел --- ответ на задачу для всех $x$ от $1$ до $n$.