K. The Tree Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$a$$$ be a sequence of integers and $$$k$$$ be a given integer. Define $$$f(a)$$$ to be the largest element that appears at least $$$k$$$ times in the sequence. Specially, if all elements of $$$a$$$ occur less than $$$k$$$ times, then $$$f(a)=0$$$.

You are given an undirected tree with $$$n$$$ vertices rooted at vertex $$$1$$$. Recall that a tree is a connected acyclic graph. Each vertex $$$i$$$ has a value $$$v_i$$$ assigned to it. We say that $$$j$$$ is in the subtree of $$$i$$$ if and only if:

  • $$$i=j$$$ or
  • $$$i$$$ is on the simple path from $$$j$$$ to the root.

The problem is as follows: for each vertex $$$i$$$, calculate $$$f(a_i)$$$, where $$$a_i$$$ is the sequence of $$$v_j$$$ for all $$$j$$$ in the subtree of $$$i$$$.

Input

Each test contains multiple test cases.

The first line of each test contains one integer $$$t$$$ ($$$1\le{t}\le1000$$$) – the number of test cases.

The first line of each test case contains two integers $$$n,k$$$ ($$$1\le{n}\le2\cdot{10^5}$$$, $$$1 \le k \le 2 \cdot 10^5$$$) – the number of vertices in the given tree.

The second line contains $$$n$$$ integers $$$v_1,v_2,\ldots{v_n}$$$ ($$$1\le{v_i}\le{10^9}$$$) – the value of each vertex.

Then follows $$$n-1$$$ lines:

Each line contains two integers $$$i,j$$$ ($$$1\le{i,j}\le{n}$$$) – indicating an edge between the vertices $$$i$$$ and $$$j$$$.

It is guaranteed that the given input forms a valid tree rooted at $$$1$$$.

It is further guaranteed that the sum of all $$$n$$$ across the test cases does not exceed $$$2\cdot{10^5}$$$.

Output

For each test case, output $$$n$$$ integers in a single line: the $$$i$$$-th integer represents the value $$$f(a_i)$$$.

Example
Input
3
5 2
3 3 3 3 3
1 2
3 5
2 3
5 4
5 2
4 4 3 3 5
1 2
2 3
3 4
4 5
3 3
114514 114514 114514
1 3
3 2
Output
3 3 3 0 3 
4 3 3 0 0 
114514 0 0