Counting in a DAG
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:
2
4 3
510 713 383 990
4 1
4 2
2 1
4 4
450 379 230 520
3 4
2 4
2 3
2 4
Output:
510 1223 383 2213
450 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