题目描述

译自 ROI 2022 Day2 T4. Большие вызовы

在「天狼星」的项目期间，一支团队正在设计工业机器人。

机器人将为排成一排的 $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$。更正式地说，类型为 $1$ 的机器人 $j$ 的作用范围将变为 $[\min(l_j, x), \max(r_j, x)]$。

对于每个 $x$ 从 $1$ 到 $n$，计算如果编号为 $x$ 的容器是最重要的容器，并且机器人以最佳方式工作，机器人能够总共放入容器的最大零件数量。

输入格式

输入包含多组数据。第一行包含一个整数 $t\ (1 \leq t \leq 2\cdot 10^5)$，表示数据组数。每组数据的格式如下：

每组输入数据的第一行包含两个整数 $n,m\ (1 \le n, m \le 2\cdot 10^5)$，分别表示容器和机器人的数量。

接下来的第二行包含 $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 2\cdot 10^5, \sum m \leq 2\cdot 10^5$。

输出格式

对于每组输入数据，输出 $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

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。