Description

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

Input Format

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

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

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

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

Output Format

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

Hint

对于 $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\}$。