Background

Translated from ROI 2022 D2T4.

In the design class at the Sirius Educational Center, a team designed an industrial robot. These robots will put parts into $n$ containers numbered from $1$ to $n$. Each container can hold at most $a_i$ parts.

There are $m$ robots in total. Initially, robot $j$ has $c_j$ parts. Also, robot $j$ has a working range determined by two numbers $l_j$ and $r_j$, meaning it can only put parts into containers with indices from $l_j$ to $r_j$ (inclusive). Robots try to put as many parts as possible into the containers.

Robots are of two types. If a robot has type $t_j = 0$, then its working range always stays unchanged. If a robot has type $t_j = 1$, it can change its working range. If the container numbered $x$ is designated as the most important container, then the working range of every type $1$ robot will expand so that this range contains container $x$. In other words, for a type $1$ robot $j$, its working range will become $[\min(l_j,x),\max(r_j,x)]$.

Problem Description

For each $x$ from $1$ to $n$, compute the maximum number of parts that the robots can put into the containers when container $x$ is considered the most important container.

Input Format

This problem has multiple test cases. The first line contains an integer $t$, the number of test cases.

For each test case, the first line contains two integers $n$ and $m$, the number of containers and the number of robots.

The next line contains $n$ integers $a_1,a_2,\dots,a_n$, the capacities of the containers.

Each of the next $m$ lines contains four integers $l_j, r_j, c_j, t_j$, describing the robot's working range, the number of parts it initially carries, and the robot type.

Output Format

For each test case, output $n$ integers, representing the answers for all $x$ from $1$ to $n$.

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

8 7 7 8

Hint

For $100\%$ of the testdata, $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\}$.

Translated by ChatGPT 5