K-th smallest weight on a tree path

You are given a tree with $N$ vertices. A tree is a connected undirected graph with no cycle. Vertices are numbered from 1 to $N$, edges are numbered from 1 to $N-1$, and every vertex carries one weight.

Write a program that answers the following query.

• u v k: print the $k$-th smallest weight among the weights of the vertices on the path from vertex $u$ to vertex $v$.

A tree has exactly one path between two vertices, and that path includes both endpoints $u$ and $v$. Equal weights on different vertices are counted separately when ranking. If the weights on the path are 3, 7, 7, 9, then both the 2nd smallest and the 3rd smallest value are 7.

The first line contains the number of vertices $N$. ($2 \le N \le 100{,}000$)

The second line contains the weights of vertex 1 through vertex $N$ in order. Each weight is a natural number not greater than $1{,}000{,}000$.

Each of the next $N-1$ lines contains two vertex numbers $u$ and $v$ joined by edge $i$.

The next line contains the number of queries $M$. ($1 \le M \le 100{,}000$)

Each of the next $M$ lines contains one query in the form u v k. Both $u$ and $v$ are vertex numbers and they may be equal. $k$ is a natural number not greater than the number of vertices on the path from $u$ to $v$.

Print the answer to each query on its own line, in the order the queries are given.