### Test Question

The lovely WrongAnswer is very fond of independent set problems. For his thesis defense in CTSC2017, he prepared a paper on independent sets.

One day, WrongAnswer decided he would use this paper to set a question. The question he eventually came up with was:

• Given a tree of $$n$$ vertices $$T = (V, E)$$ and an independent set $$I$$, find the independent set whose lexicographical order is exactly $$k$$ larger than $$I$$.
WrongAnswer asks you to test this problem for him. Here are some definitions that may be useful:
• An independent set $$I$$ is a subset of $$V$$ satisfying the condition that any two vertices in $$I$$ are not adjacent in the tree. In other words, there are no two vertices $$x, y \in I$$ with $$(x, y) \in E$$.
• Suppose you have two vertex sets $$A, B$$. Let the vertex indices in $$A$$ be $$a_1, a_2, \ldots, a_{|A|}$$ in ascending order; and similarly, let the indices in $$B$$ be $$b_1, b_2, \ldots, b_{|B|}$$ in ascending order. Then, $$A$$ is lexicographically smaller than $$B$$ if on the lowest $$i$$ where $$a_i$$ and $$b_i$$ differ, $$a_i < b_i$$.
If all independent sets of $$T$$ were sorted lexicographically under these definitions, $$I$$ would be the $$x^{th}$$ set in the order. Output the $$(x + k)^{th}$$ set in the order, or the empty set if no such set exists.

### Limits

$$1 \leq n \leq 10^6$$
$$1 \leq k \leq 10^{18}$$

1 6 $$1 \leq n \leq 20$$
2 17 $$1 \leq n \leq 2000$$
$$1 \leq k \leq 10000$$
3 21 $$1 \leq n \leq 2000$$
4 27 The tree is a line; every vertex has degree at most 2.

### Input format

The first line contains one integer $$n$$.

The second line contains one integer $$k$$.

The third line contains $$n - 1$$ integers, the $$i^{th}$$ of which represents the first endpoint of the $$i^{th}$$ edge (vertices 0-indexed).

The fourth line contains $$n - 1$$ integers, the $$i^{th}$$ of which represents the second endpoint of the $$i^{th}$$ edge.

The fifth line contains one integer $$|I|$$, the size of $$I$$.

The sixth line contains $$I$$ integers $$I_1, I_2, \ldots, I_{|I|}$$, representing the elements of $$I$$. It is guaranteed that $$I$$ is a valid independent set.

### Output format

Let your answer be the independent set $$S$$ (If there is no valid $$S$$, let $$S = \emptyset$$). Output one line containing $$|S|$$ integers, the elements of $$S$$ in ascending order.

### Samples

 Sample Input 1 Sample Output 1 10 4 0 1 1 1 1 4 0 7 0 1 2 3 4 5 6 7 8 9 3 5 8 9 6 7 9

### Submitting .cpp to 'thesis'

Time Limit: 10 Seconds
Memory Limit: 1024MB
No. of ACs: 1