E. Good Game
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar went to a sports club to play some indoor games. There, he saw a pinball machine which was differently designed.

The pinball machine is a rooted tree consisting of $$$n$$$ nodes rooted at $$$1$$$, which was inverted(i.e.,the root will be the bottom of the tree). So, if we put a ball at some place, it will reach downwards due to gravity until there is a possible movement (i.e., until there is no ball in the next node).

You will be given $$$m$$$ balls initial positions and put them sequentially on the pinball machine.

Tell the final positions of $$$m$$$ balls on the pinball machine. If there is a ball already in the mentioned position, tell $$$-1$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{5}$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,m$$$ $$$(1 \le n,m \le 10^{6})$$$ — the number of nodes in the pinball machine and the number of balls.

The next $$$n-1$$$ lines contain two integers $$$u,v$$$ $$$(1 \le u,v \le n, u≠v)$$$ — there is an edge connecting $$$u$$$ and $$$v$$$.

The next line contains $$$m$$$ space separated integers $$$x_i$$$ $$$(1 \le x_i \le n, 1 \le i \le m)$$$ — the initial positions of $$$m$$$ balls.

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^{6}$$$.

Output

For each testcase, print $$$m$$$ space separated integers — the final positions of $$$m$$$ balls.

Example
Input
2
7 8
1 2
1 3
2 4
2 5
3 6
3 7
1 2 3 4 5 6 7 1
5 5
1 2
5 3
4 3
3 1
4 4 4 5 2
Output
1 2 3 4 5 6 7 -1 
1 3 4 5 2
Note

In the $$$2^{nd}$$$ testcase,

The movement of the $$$1^{st}$$$ ball is $$$4$$$ $$$\rightarrow$$$ $$$3$$$ $$$\rightarrow$$$ $$$1$$$, hence the final position is $$$1$$$.

The movement of the $$$2^{st}$$$ ball is $$$4$$$ $$$\rightarrow$$$ $$$3$$$, hence the final position is $$$3$$$.