P11103 [ROI 2022] 挑战 (Day 2)

翻译自 [ROI 2022 D2T4](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。 在天狼星教育中心的设计班中，一个团队的成员设计了一种工业机器人。这种机器人将把零件放入标号从 $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$ 的问题的答案。

对于 $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\}$。 | Subtask | 分值 | $\sum n\le$ | $\sum m\le$ | 其它特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $100$ | $100$ | $m=1$ | | $2$ | $7$ | $100$ | $100$ | | | $3$ | $6$ | $2000$ | $2000$ | | | $4$ | $6$ | $20000$ | $200$ | | | $5$ | $12$ | $10^5$ | $2000$ | | | $6$ | $17$ | $20000$ | $20000$ | $t_i=1$ | | $7$ | $8$ | $10^5$ | $10^5$ | $l_i\le l_{i+1},r_i\le r_{i+1},t_i=1$ | | $8$ | $8$ | $10^5$ | $10^5$ | $t_i=1$ | | $9$ | $13$ | $10^5$ | $10^5$ | 对于所有 $t_i=0$ 的机器人，$r_i\le50$ 或 $l_i>n-50$ | | $10$ | $4$ | $10^5$ | $10^5$ | $a_i=1$ | | $11$ | $6$ | $10^5$ | $10^5$ | | | $12$ | $3$ | $2\times10^5$ | $2\times10^5$ | |