Askhat is a prospective businessman. He quickly figured that programming is an unprofitable business, so he decided to open a chicken farm.

His farm consists of $n$ chickens ordered in a row. The $i$-th chicken can eat at most $a_i$ grains. There are $m$ feeders, each described by integers $l_j, r_j, c_j$. The $j$-th feeder can feed the $i$-th chicken if $l_j \le i \le r_j$, and there are $c_j$ grains in this feeder.

Turns out that every business has its own pitfalls, in this case it has the face of chicken feeding control, represented by Ildar. He claims that every respectable chicken farm must have a chicken representative. That is, there must exist a chicken $i$ such that $l_j \le i \le r_j$ holds for every feeder $j$. All feeders that don’t obey this rule must be exterminated.

Now Askhat asks you to find, for each $i$, what is the maximum number of grains that can be fed to chickens if we leave only feeders that can feed chicken $i$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers $n, m$ ($1 \le n, m \le 10^5$) — the number of chickens and the number of feeders respectively.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the number of grains that chickens can eat.

Each of the next $m$ lines contains three integers $l_j, r_j, c_j$ ($1 \le l_j \le r_j \le n, 0 \le c_j \le 10^9$) — description of the $j$-th feeder.

It is guaranteed that both the sum of $n$ and the sum of $m$ for all test cases do not exceed $10^5$.

Output

For each test case, print $n$ integers — the answer to the problem.

Examples

Input 1

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

Output 1

2 5 2 0