Soit un arbre (graphe connexe sans cycle) de $N$ sommets. Les sommets sont numérotés de $1$ à $N$ et les arêtes de $1$ à $N-1$. Chaque sommet possède un poids.

Écrivez un programme qui exécute la requête suivante :

• u v k : afficher le $k$-ième plus petit poids parmi les poids des sommets situés sur le chemin de $u$ à $v$.

Entrée

La première ligne contient $N$ ($2 \le N \le 100\,000$).

La deuxième ligne contient les poids des sommets dans l’ordre du sommet $1$ au sommet $N$.

Les $N-1$ lignes suivantes contiennent deux entiers $u$ et $v$, les deux sommets reliés par l’arête $i$.

La ligne suivante contient le nombre de requêtes $M$ ($1 \le M \le 100\,000$).

Les $M$ lignes suivantes contiennent chacune une requête.

Les poids des sommets sont toujours des entiers naturels inférieurs ou égaux à $1\,000\,000$.

Sortie

Afficher le résultat de chaque requête, dans l’ordre, une par ligne.

Exemples

Entrée 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

Sortie 1

2
8
9
105
7