Вам дано корневое дерево, состоящее из $$$n$$$ вершин. Корень находится в вершине $$$1$$$. В каждой вершине записано некоторое число: в $$$i$$$-й вершине — $$$val_i$$$.
Вы должны обработать $$$q$$$ запросов к дереву, $$$i$$$-й запрос задается двумя вершинами $$$u_i$$$ и $$$v_i$$$. Для ответа на запрос нужно рассмотреть все вершины $$$w$$$, которые лежат в поддереве $$$u_i$$$ или $$$v_i$$$ (если вершина лежит в обоих поддеревьях, она учитывается дважды). Нужно выписать все числа на вершинах в этой паре поддеревьев и найти то из них, которое встречается наибольшее количество раз (если таких несколько — минимальное из них).
В первой строке записано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве. Во второй строке записаны $$$n$$$ целых чисел $$$val_1, val_2, \dots, val_n$$$ ($$$1 \le val_i \le 2 \cdot 10^5$$$) — числа, записанные в вершинах.
Затем идет $$$n - 1$$$ строка, в каждой записаны по два числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$), представляющие ребро между вершинами $$$x$$$ и $$$y$$$. Данные ребра составляют дерево.
В следующей строке записано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов, которые требуется обработать.
Затем идут $$$q$$$ строк, в $$$i$$$-й из них записаны два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — корни поддеревьев в $$$i$$$-м запросе.
Для каждого запроса выведите ответ на него — целое число, которое встречается наибольшее количество раз в паре поддеревьев из запроса (если таких чисел несколько — минимальное из них).
8 2 1 3 2 3 3 2 4 1 2 1 3 2 4 3 5 3 6 3 7 7 8 6 2 7 3 7 2 3 1 1 5 6 1 3
2 3 3 2 3 3
В $$$1$$$-м запросе пара поддеревьев содержит вершины $$$[2, 4, 7, 8]$$$, на которых записаны числа $$$\{1, 2, 2, 4\}$$$. Число $$$2$$$ встречается дважды, все остальные — не более одного раза, поэтому ответ на запрос — $$$2$$$.
Во $$$2$$$-м запросе пара поддеревьев содержит вершины $$$[3, 5, 6, 7, 7, 8, 8]$$$, на которых записаны числа $$$\{3, 3, 3, 2, 2, 4, 4\}$$$. Число $$$3$$$ встречается наибольшее количество раз.
В $$$4$$$-м запросе пара поддеревьев содержит вершины $$$[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8]$$$, на которых записаны числа $$$\{2, 2, 1, 1, 3, 3, 2, 2, 3, 3, 3, 3, 2, 2, 4, 4\}$$$. Чаще всего встречаются числа $$$2$$$ и $$$3$$$, минимальное из них — $$$2$$$.
