You are given a tree of $$$n$$$ nodes, where node $$$i$$$ has weight $$$w_i$$$, and an integer $$$k$$$.

Let the tree be rooted at node $$$x$$$. You may select a subset $$$S$$$ of the nodes such that $$$|S| = k$$$ and $$$x \in S$$$. Let $$$f(i)$$$ be the sum of the weights of all nodes in $$$S$$$ on the path from node $$$i$$$ to the root. The score of $$$S$$$ is $$$\sum_{i \in S} f(i)$$$.

For each node $$$1 \le x \le n$$$, find the maximum possible score among all subsets $$$S$$$ if the tree is rooted at node $$$x$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 4000$$$, $$$1 \le k \le n$$$).

The second line of each test case contains $$$n$$$ integers $$$w_1, w_2,\ldots, w_n$$$ ($$$1 \le w_i \le 10^9$$$).

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), indicating that nodes $$$u$$$ and $$$v$$$ are connected by an edge. It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4000$$$.

Output

For each test case, print $$$n$$$ integers. For each $$$x$$$ from $$$1$$$ to $$$n$$$, print the maximum possible score among all subsets $$$S$$$ if the tree is rooted at node $$$x$$$.

Note

In the first test case, the tree is as follows:

$\text{[math]}$

For each $$$1 \le x \le n$$$, the following is an optimal set $$$S$$$:

$$$x = 1$$$: $$$S = \{1, 2, 5\}$$$; the score is $$$(2) + (12 + 2) + (9 + 2) = 27$$$,
$$$x = 2$$$: $$$S = \{2, 4 ,5\}$$$; the score is $$$(12) + (6 + 12) + (9 + 6 + 12) = 57$$$,
$$$x = 3$$$: $$$S = \{2, 3, 5\}$$$; the score is $$$(12 + 3) + (3) + (9 + 3) = 30$$$,
$$$x = 4$$$: $$$S = \{2, 4, 5\}$$$; the score is $$$(12 + 6) + (6) + (9 + 6) = 39$$$,
$$$x = 5$$$: $$$S = \{2, 4 ,5\}$$$; the score is $$$(12 + 6 + 9) + (6 + 9) + (9) = 51$$$,
$$$x = 6$$$: $$$S = \{2 ,4, 6\}$$$; the score is $$$(12 + 6 + 7) + (6 + 7) + (7) = 45$$$.

In the second test case, $$$S = \{1, 2, 3, 4, 5\}$$$ for all $$$x$$$.

The Endians

Examples