F1. Несоответствие частот (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
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$$$, $$$k = 1$$$).

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

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

Пример
Входные данные
5
5 2 3 4 3
1 2
1 3
2 4
2 5
3
1 4 4 5 1
2 3 2 3 1
5 5 4 3 1
Выходные данные
1 5
0
1 2
Примечание

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

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

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