is a strong rowing team. As one of the three members, Apollo wants to help his teammates to solve tree problems faster. He plans to leave a tree problem to his teammates every day to train them. If his teammates failed to solve it, as a punishment, they would have to take turns to pay Apollo for a day's meal.
Today is the first day for them to execute the plan. Facing Apollo's tough problem, his teammates decide to ask you for help. In return, they promise to give you half of the money that is saved for not having to pay Apollo's meal. Smart as you are, could you help them solve the following problem and get this huge sum (Apollo eats a lot)?
Given a tree with n nodes numbered from 1 to n. The node 1 is the root. Each node i has an associated value v[i]. Denote K as the distance coefficient, and W as the target value.
Denote the depth of node i as dep[i]. The depth of node 1 (dep[1]) is 1. For each node, its is defined as follows:

•  For some array c, let's denote a lili sequence as a sequence of indices such that , and for each , is the minimum number such that and .
•  If the simple path from to consists of m nodes namely , then the of path from to is the length of 's longest lili sequence.
•  For nodes satisfying : Let u be the node on the path from node 1 (root) to node i, whose distance to node i is K (that is, the path beginning from u to i including both ends has a total of K nodes). The of node i equals to the of path from u to i.
•  For nodes satisfying dep[i] < K: The of node i equals to the of path from 1 to i.
  

The first line is an integer  (), which is the number of test cases.
Each test case begins with a line containing two integers ,  
The second line The second line contains n space-separated integers v[1], v[2], ..., v[n]  --- values of the nodes.
Each of the next n - 1 lines contain two integers u, v , denoting an edge between node u and node v exists in the tree. 
It's guaranteed that the given edges form a tree.

For each test case, you should print exactly one line contains n positive integers as answers for all K from 1 to n.

2
5 3
1 5 2 4 3
1 2
2 3
3 4
4 5
5 2
1 5 7 4 6
1 2
1 3
2 4
2 5

0 0 0 0 0
0 3 4 4 4

Explanation to the second sample:
K=1,The lili value of node {1,2,3,4,5} is {1,1,1,1,1}
K=2,The lili value of node {1,2,3,4,5} is {1,2,2,1,2}
K=3,The lili value of node {1,2,3,4,5} is {1,2,2,2,3}
K=4,The lili value of node {1,2,3,4,5} is {1,2,2,2,3}
K=5,The lili value of node {1,2,3,4,5} is {1,2,2,2,3}