Имеется дерево (связный неориентированный граф без циклов) из $N$ вершин. Вершины пронумерованы от $1$ до $N$, рёбра пронумерованы от $1$ до $N-1$. Каждая вершина имеет вес. Напишите программу, которая выполняет следующие запросы:

u v k: выведите $k$-й наименьший вес среди вершин на пути от $u$ до $v$.

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

В первой строке дано $N$ ($2 \le N \le 100\,000$).

Во второй строке даны веса вершин в порядке от вершины $1$ до вершины $N$.

В следующих $N-1$ строках даны номера двух вершин $u$ и $v$, соединённых $i$-м ребром.

В следующей строке дано количество запросов $M$ ($1 \le M \le 100\,000$).

В следующих $M$ строках даны запросы, по одному на строке.

Веса вершин — натуральные числа, не превосходящие $1\,000\,000$.

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

Для каждого запроса выведите результат в отдельной строке в порядке поступления запросов.

Примеры

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

8
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
5
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2

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

2
8
9
105
7