큰 도전

Sirius 교육센터의 프로젝트 주간에서 한 팀의 참가자들이 산업용 로봇을 설계합니다. 1번부터 $n$번까지 번호가 매겨진 $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 \le t \le 200000$)가 주어집니다. 각 묶음의 첫 줄에는 컨테이너 수와 로봇 수를 나타내는 정수 $n$, $m$ ($1 \le n, m \le 200000$)이 주어집니다. 다음 줄에는 컨테이너의 용량 $a_i$ ($0 \le a_i \le 10^9$) $n$개가 주어집니다. 이어지는 $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\}$)가 주어집니다. 순서대로 로봇의 작용 범위, 처음 가진 부품 수, 종류입니다. 한 테스트에 있는 모든 입력 묶음에 대해 $n$의 합을 $\sum n$, $m$의 합을 $\sum m$이라 할 때, $\sum n \le 200000$이고 $\sum m \le 200000$이 보장됩니다.

각 입력 묶음마다 $x$가 1부터 $n$까지일 때의 답을 $n$개의 정수로 출력합니다.