There are $n$ chickens standing in a row, where the $i$-th chicken can eat at most $a_i$ grains.

There are $m$ porters. The $j$-th porter can feed grains to chickens $l_j, l_j+1, \dots, r_j$, and carries $c_j$ grains. A porter does not need to feed all the grains they carry; they only need to ensure that the total amount of grains fed does not exceed $c_j$.

For each $i$, calculate the maximum total amount of grains that can be fed if only the porters satisfying $l_j \le i \le r_j$ are kept.

Input

The first line of each test case contains a positive integer $T$, representing the number of test cases. The format for each test case is as follows:

The first line contains two positive integers $n$ and $m$, representing the number of chickens and porters, respectively.

The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$, representing the amount of grains each chicken can eat.

The next $m$ lines each contain three integers $l_j, r_j, c_j$, describing the $j$-th porter.

Output

For each test case, output a single line containing $n$ non-negative integers, representing the answers.

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

Input 2

See ex_2.in/ex_2.ans in the provided files.

Constraints

This problem uses subtask-based testing.

For all data, it is guaranteed that $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$, and $0 \le c_j \le 10^9$.