1227 : 茶和咖啡

Description

中山大学的女孩们喜欢喝茶。但是有一天，她们想要变换口味，所以决定在接下来的 \(n\) 天里尝试一下喝咖啡。

现在，总是为中山大学提供食物和饮料的 Zayin 决定去商店买一些咖啡，她了解到第 \(i\) 天的价格是 \(a_i\)。同时，她有 \(m\) 张优惠券 — 第 \(i\) 张优惠券可以在前 \(r_i\) 天（包括第 \(r_i\) 天）使用，并且可以将当天咖啡的价格减少 \(w_i\)。

请注意，每张优惠券只能使用一次，Zayin 可以在一天内使用多张优惠券。使用优惠券后，价格可以是负数。

由于中山大学的女孩们仍然需要喝茶，Zayin 决定选择只在某些天内购买咖啡。现在她想知道，如果她选择恰好 \(k\ (1\le k \le n)\) 天来购买咖啡，她需要花费的最少金额（或者她可以获得的最大金额）是多少呢？

Input

输入的第一行包含一个整数 \(t\ (1\le t\le 10)\) — 表示测试用例的数量。接下来是测试用例的描述。

第一行包含两个整数 \(n,m\ (1\le n, m\le 2\times 10^5)\) — 表示天数和优惠券的数量。

第二行包含 \(n\) 个整数 \(a_1,a_2,\cdots,a_n\ (1\le a_i \le 10^9)\) — 其中 \(a_i\) 表示第 \(i\) 天咖啡的价格。

接下来的 \(m\) 行，每行包含两个整数 \(r_i,w_i\ (1\le r_i\le n,\ 1\le w_i\le 10^9)\) — 表示第 \(i\) 张优惠券可以在前 \(r_i\) 使用，并且可以将价格减少 \(w_i\)。

Output

对于每个测试用例，输出 \(n\) 个整数 — 第 \(i\) 个整数表示 Zayin 恰好选择 \(i\) 天购买咖啡时所花费的最少金额。

Sample

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 

Hint

Source