## DAGCNT2 - Counting in a DAG

no tags

You are given a weighted DAG. For each vertex, calculate the sum of the weights of the vertices within its reach (including itself).

### Input

The first line contains an integer T, denoting the number of test cases.

For each test case, the first line contains two positive integers n and m, denoting the number of vertices and the number of edges in the DAG.

The second line contains n positive integers w1..wn, denoting the weights of vertices.

The next m lines contain two positive integers u,v, denoting an edge from u to v.

### Output

For each test case, print a line consisting of n numbers, denoting the sum for each vertex.

### Example

`Input:24 3510 713 383 990 4 14 22 14 4450 379 230 520 3 42 42 32 4Output:510 1223 383 2213450 1129 750 520`

### Constraints

Input Set 1: numberOfTestCases <= 40, n <= 100, m <= 10000

Input Set 2: numberOfTestCases <= 2, n <= 1000, m <= 500000

Input Set 3: numberOfTestCases <= 2, n <= 20000, m <= 500000

The weights are no more than 1000