Вам дано корневое дерево, состоящее из \(n\) вершин. Корень находится в вершине \(1\). В каждой вершине записано некоторое число: в \(i\)-й вершине — \(val_i\).
Вы должны обработать \(q\) запросов к дереву, \(i\)-й запрос задается двумя вершинами \(u_i\) и \(v_i\). Для ответа на запрос нужно рассмотреть все вершины \(w\), которые лежат в поддереве \(u_i\) или \(v_i\) (если вершина лежит в обоих поддеревьях, она учитывается дважды). Нужно выписать все числа на вершинах в этой паре поддеревьев и найти то из них, которое встречается наибольшее количество раз (если таких несколько — минимальное из них).
Примечание
В \(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\).