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.

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.

Frequency Mismatch (Hard Version)

Examples