给你一棵由 $$$n$$$ 个顶点组成的有根树。顶点 $$$1$$$ 是根。每个顶点上都写有一个整数;对于顶点 $$$i$$$,该整数是 $$$val_i$$$。
您将获得对树的 $$$q$$$ 查询。第 $$$i$$$ 查询由两个顶点 $$$u_i$$$ 和 $$$v_i$$$ 表示。要回答该查询,请考虑位于 $$$u_i$$$ 或 $$$v_i$$$ 的子树中的所有顶点 $$$w$$$(如果一个顶点位于两个子树中,则计算两次)。对于这两个子树中的所有顶点,列出其上写的所有整数,并找到出现次数最多的整数。如果存在多个出现次数最多的整数,则其中出现次数最少的就是答案。
输入
第一行包含一个整数 $$$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$$$ 查询中子树的根。
输出
对于每个查询,打印一个整数 - 在相应的子树对中出现次数最多的数字(如果有多个这样的数字,则打印其中最小的一个)。
示例
输入 #1
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
输出 #1
2 3 3 2 3 3
注意
在$$$1$$$-st查询中,这对子树由顶点$$$[2, 4, 7, 8]$$$组成,其上写的数字是$$$\{1, 2, 2, 4\}$$$。数字 $$$2$$$ 出现两次,所有其他数字最多出现一次,所以答案是 $$$2$$$。
在$$$2$$$-nd查询中,这对子树由顶点$$$[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$$$。