Hay un árbol (grafo conexo sin ciclos no dirigido) compuesto por $N$ vértices. Los vértices están numerados del $1$ al $N$, y las aristas están numeradas del $1$ al $N-1$. Cada vértice tiene un peso.

Escribe un programa que realice la siguiente consulta:

• u v k: Imprime el $k$-ésimo peso más pequeño entre los pesos de los vértices en el camino de $u$ a $v$.

Entrada

La primera línea contiene $N$ ($2 \le N \le 100{,}000$).

La segunda línea contiene los pesos de los vértices en orden desde el vértice $1$ hasta el vértice $N$.

Las siguientes $N-1$ líneas contienen dos números $u$ y $v$ que indican los dos vértices conectados por la arista $i$.

La siguiente línea contiene el número de consultas $M$ ($1 \le M \le 100{,}000$).

Las siguientes $M$ líneas contienen una consulta por línea.

Los pesos de los vértices son siempre números naturales menores o iguales a $1{,}000{,}000$.

Salida

Imprime el resultado de cada consulta en una línea, en orden.

Ejemplos

Entrada 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

Salida 1

2
8
9
105
7