F2. Несоответствие частот (сложная версия)
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие между версиями — ограничение на $$$k$$$. Вы можете делать взломы, только если обе версии задачи решены.

Вам дано неориентированное дерево из $$$n$$$ вершин. На каждой вершине $$$v$$$ записано значение $$$a_v$$$. Вы должны ответить на запросы, связанные с деревом.

Вам дано $$$q$$$ запросов. В каждом запросе дается $$$5$$$ целых чисел, $$$u_1, v_1, u_2, v_2, k$$$. Обозначим количество вершин со значением $$$c$$$ на пути $$$u_1 \rightarrow v_1$$$ как $$$x_c$$$, а количество вершин со значением $$$c$$$ на пути $$$u_2 \rightarrow v_2$$$ как $$$y_c$$$. Пусть существует $$$z$$$ таких значений $$$c$$$, что $$$x_c \neq y_c$$$. Тогда выведите любые $$$\min(z, k)$$$ таких значений в любом порядке.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество вершин в дереве.

Следующая строка содержит $$$n$$$ целых чисел, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — значения, записанные на каждой вершине дерева.

Затем следует $$$n - 1$$$ строка. Каждая строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n, u \neq v$$$), обозначающие ребро дерева. Гарантируется, что заданные ребра образуют дерево.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов.

Затем следуют $$$q$$$ строк. Каждая строка содержит пять целых чисел $$$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$$$).

Выходные данные

Для каждого запроса выведите ответ на отдельной строке. Для каждого запроса сначала выведите $$$\min(z, k)$$$, а затем в той же строке выведите любые $$$\min(z, k)$$$ значений, которые встречаются разное количество раз на путях, в любом порядке.

Пример
Входные данные
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
Выходные данные
2 3 5
0
1 5
3 5 2 4
Примечание

Для $$$1$$$ запроса первый путь: $$$1 \rightarrow 2 \rightarrow 4$$$, на котором встречается мультинабор значений $$$\{5, 2, 4\}$$$. На втором пути $$$4 \rightarrow 2 \rightarrow 5$$$ мы имеем мультинабор $$$\{4, 2, 3\}$$$. Два числа — $$$3$$$ и $$$5$$$ встречаются разное количество раз, поэтому мы выводим оба числа.

Во $$$2$$$ запросе пути совпадают, поэтому выводим $$$0$$$.

В $$$3$$$ запросе у нас те же пути, что и в запросе $$$1$$$, но нам нужно вывести только $$$1$$$ значение, поэтому мы выводим $$$5$$$.

В $$$4$$$ запросе первый путь — только вершина $$$5$$$, что приводит к мультинабору $$$\{3\}$$$, а второй путь — $$$4 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$ дает $$$\{4, 2, 5, 3\}$$$. Числа $$$5$$$, $$$2$$$ и $$$4$$$ встречаются разное количество раз.