题目背景

翻译自 ROI 2022 D2T4。

在天狼星教育中心的设计班中，一个团队的成员设计了一种工业机器人。这种机器人将把零件放入标号从 $1$ 到 $n$ 的 $n$ 个容器中。每个容器最多可以放置 $a_i$ 个零件。

一共有 $m$ 台机器人。初始时，第 $j$ 台机器人有 $c_j$ 个零件。此外，第 $j$ 台机器人有一个工作范围，由两个数字 $l_j$ 和 $r_j$ 确定，表示机器人只能将零件放入编号从 $l_j$ 到 $r_j$ 的容器中（包括边界）。机器人试图尽可能多地将零件放入容器。

机器人分为两种类型。如果机器人的类型 $t_j = 0$，则其工作范围始终保持不变。而机器人类型 $t_j = 1$ 可以改变它的工作范围。如果将编号为 $x$ 的容器指定为最重要的容器，则每个类型为 $1$ 的机器人的工作范围将扩大，来使这个范围包含容器 $x$。或者说，具有类型 $1$ 的机器人 $j$ 的工作范围将改变为 $[\min(l_j,x),\max(r_j,x)]$。

题目描述

对于从 $1$ 到 $n$ 的每个 $x$，计算在容器 $x$ 被视为最重要的容器时，机器人们最多能够将多少零件放入容器中。

输入格式

本题有多组数据。第一行给出一个整数 $t$，表示数据的组数。

每组输入数据的第一行给出两个整数 $n$ 和 $m$，分别表示容器和机器人的数量。

接下来一行给出 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示容器的容量。

接下来的 $m$ 行中的每一行都包含四个整数 $l_j，r_j，c_j，t_j$，表示机器人的工作范围、刚开始携带的零件数量和机器人类型。

输出格式

对于每组输入数据，输出 $n$ 个整数，表示对于从 $1$ 到 $n$ 的所有 $x$ 的问题的答案。

1
4 3
3 3 2 2
1 2 2 0
3 3 3 0
2 2 4 1

8 7 7 8

提示

对于 $100\%$ 的数据，$1 \le t \le 200000$，$1 \le n,m \le 200000$，$0 \le a_i \le 10^9$，$1 \le l_j \le r_j \le n$，$0 \le c_j \le 10^9$，$t_j \in \{0, 1\}$。