Dane jest drzewo (nieskierowany graf spójny bez cykli) składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a krawędzie od $1$ do $N-1$. Każdy wierzchołek ma wagę.

Napisz program wykonujący następujące zapytanie:

• u v k: Wypisz $k$-tą najmniejszą wagę spośród wag wierzchołków na ścieżce z $u$ do $v$.

Wejście

W pierwszym wierszu podana jest liczba $N$ ($2 \le N \le 100{,}000$).

W drugim wierszu podane są wagi wierzchołków w kolejności od wierzchołka $1$ do $N$.

W kolejnych $N-1$ wierszach podane są dwie liczby $u$ i $v$ oznaczające krawędź $i$ łączącą wierzchołki $u$ i $v$.

Następny wiersz zawiera liczbę zapytań $M$ ($1 \le M \le 100{,}000$).

Kolejne $M$ wierszy zawiera po jednym zapytaniu w każdym wierszu.

Wagi wierzchołków są zawsze liczbami naturalnymi nie większymi niż $1{,}000{,}000$.

Wyjście

Dla każdego zapytania wypisz wynik w osobnej linii, w kolejności zapytań.

Przykład

Wejście 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

Wyjście 1

2
8
9
105
7