Yet Another Coffee
Description
The girls of SYSU like drinking tea. But one day, they wanted a change and decided to try coffee in the next $n$ days.
Now Zayin, who always provides food and drinks for SYSU, will go to the shop to buy some coffee. She learns that the price of day $i$ is $a_i$. Meanwhile, she has $m$ coupons - the $i$ coupon can be used before day $r_i$ (inclusively) and can reduce the price of coffee on that day by $w_i$.
Notice that each coupon can be used only once and Zayin can use more than one coupon per day. The price can be a negative number after using the coupons.
Since the girls of SYSU still need to drink tea, Zayin decided to choose some days to buy coffee. Now she wants to know the minimum money she will spend (or the maximum money she can get) if she chooses exactly $k\ (1\le k \le n)$ days to buy coffee.
The first line of the input contains a single integer $t\ (1\le t\le 10)$ — the number of test cases. The description of the test cases follows.
The first line contains two integers $n,m\ (1\le n, m\le 2\times 10^5)$ - the number of days and the number of coupons.
The second line contains $n$ integers $a_1,a_2,\cdots,a_n\ (1\le a_i \le 10^9)$ - $a_i$ denotes the price of coffee on day $i$.
Next $m$ lines, each line contains two integers $r_i,w_i\ (1\le r_i\le n,\ 1\le w_i\le 10^9)$, denoting that the $i$ th coupon can be used before day $r_i$ and can reduce the price by $w_i$.
For each testcase, output $n$ integers - the $i$ th integer represents the minimum money Zayin will spend to buy coffee if she chooses exactly $i$ days to buy coffee.
Notice that the answer can be a negative integer.
Input
The first line of the input contains a single integer $t\ (1\le t\le 10)$ — the number of test cases. The description of the test cases follows.
The first line contains two integers $n,m\ (1\le n, m\le 2\times 10^5)$ - the number of days and the number of coupons.
The second line contains $n$ integers $a_1,a_2,\cdots,a_n\ (1\le a_i \le 10^9)$ - $a_i$ denotes the price of coffee on day $i$.
Next $m$ lines, each line contains two integers $r_i,w_i\ (1\le r_i\le n,\ 1\le w_i\le 10^9)$, denoting that the $i$ th coupon can be used before day $r_i$ and can reduce the price by $w_i$.
Output
For each testcase, output $n$ integers - the $i$ th integer represents the minimum money Zayin will spend to buy coffee if she chooses exactly $i$ days to buy coffee.
Notice that the answer can be a negative integer.
2
5 2
1 2 3 4 5
3 1
4 2
7 3
4 3 1 10 3 8 6
4 9
3 8
4 5
-2 0 3 7 12
-21 -18 -15 -11 -5 3 13