【PR #8】养鸡 - Problem

有 $n$ 只鸡站成一排，第 $i$ 只鸡至多能吃 $a_i$ 的谷子。

有 $m$ 个波特，第 $j$ 个波特可以给第 $l_j,l_j+1,\cdots,r_j$ 只鸡喂谷子，并且它只携带了 $c_j$ 的谷子。波特不需要把携带的所有谷子都喂出去，只需要保证喂出去的谷子不超过 $c_j$ 即可。

对于每个 $i$ ，求出如果只保留满足 $l_j\le i\le r_j$ 的波特，那么最多一共能喂多少谷子。

每个测试点的第一行是一个正整数 $T$ ，表示数据组数。每组数据的格式如下。

第一行两个正整数 $n,m$ ，分别表示鸡和波特的数量。

第二行 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$ ，表示每只鸡能吃的谷子数量。

接下来 $m$ 行，第 $j$ 行三个整数 $l_j,r_j,c_j$ ，描述第 $j$ 个波特。

对每组数据输出一行 $n$ 个非负整数，表示答案。

2 5 2 0

见下发文件中的 ex_2.in/ex_2.ans。

本题采用子任务捆绑测试。

对于所有数据，保证 $1\le T\le 10^4,1\le \sum n,\sum m\le 10^5,0\le a_i\le 10^9,1\le l_j\le r_j\le n,0\le c_j\le 10^9$ 。

子任务编号	$\sum n,\sum m\le$	特殊性质	分值
$1$	$300$		$15$
$2$	$2000$		$15$
$3$	$10^5$	$l_j=1,r_j\le r_{j+1}$	$20$
$4$	$10^5$	$l_j\le l_{j+1},r_j\le r_{j+1}$	$25$
$5$	$10^5$		$25$

Public Judge