F2. Frequency Mismatch (Hard Version)
time limit per test
4.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the two versions of this problem is the constraint on $$$k$$$. You can make hacks only if all versions of the problem are solved.

You are given an undirected tree of $$$n$$$ nodes. Each node $$$v$$$ has a value $$$a_v$$$ written on it. You have to answer queries related to the tree.

You are given $$$q$$$ queries. In each query, you are given $$$5$$$ integers, $$$u_1, v_1, u_2, v_2, k$$$. Denote the count of nodes with value $$$c$$$ on path $$$u_1 \rightarrow v_1$$$ with $$$x_c$$$, and the count of nodes with value $$$c$$$ on path $$$u_2 \rightarrow v_2$$$ with $$$y_c$$$. If there are $$$z$$$ such values of $$$c$$$ such that $$$x_c \neq y_c$$$, output any $$$\min(z, k)$$$ such values in any order.

Input

The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of nodes in the tree.

The next line contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — the value written on each node of the tree.

Then $$$n - 1$$$ lines follow. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n, u \neq v$$$) denoting an edge of the tree. It is guaranteed that the given edges form a tree.

The next line contains one integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow. Each line contains five integers $$$u_1, v_1, u_2, v_2, k$$$ ($$$1 \leq u_1, v_1, u_2, v_2 \leq n$$$, $$$1 \leq k \leq 10$$$).

Output

For each query, output on a separate line. For a query, first output $$$\min(z, k)$$$ and then on the same line, output any $$$\min(z, k)$$$ values in any order which occur a different number of times in each path.

Example
Input
5
5 2 3 4 3
1 2
1 3
2 4
2 5
4
1 4 4 5 3
2 3 2 3 1
1 4 4 5 1
5 5 4 3 10
Output
2 3 5
0
1 5
3 5 2 4
Note

For query $$$1$$$, the first path is $$$1 \rightarrow 2 \rightarrow 4$$$, coming across the multiset of values $$$\{5, 2, 4\}$$$. On the second path $$$4 \rightarrow 2 \rightarrow 5$$$, we have the multiset $$$\{4, 2, 3\}$$$. Two numbers — $$$3$$$ and $$$5$$$ occur a different number of times, hence we print them both.

In query $$$2$$$, there is no difference between the paths, hence we output $$$0$$$.

In query $$$3$$$, we have the same paths as query $$$1$$$, but we need to output only $$$1$$$ value, hence we output $$$5$$$.

In query $$$4$$$, the first path is just the node $$$5$$$, resulting in the multiset $$$\{3\}$$$, and the second path $$$4 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$ gives $$$\{4, 2, 5, 3\}$$$. The numbers $$$5$$$, $$$2$$$ and $$$4$$$ occur a different number of times.