There is a tree (undirected connected graph without cycles) consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$. Each vertex has a weight.

Write a program that processes the following queries:

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

Input

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

The second line contains the weights of the vertices in order from vertex $1$ to vertex $N$.

The next $N-1$ lines each contain two vertex numbers $u$ and $v$ connected by the $i$-th edge.

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

The next $M$ lines each contain one query.

The weight of a vertex is always a natural number less than or equal to $1{,}000{,}000$.

Output

For each query, output the result in order, one per line.

Examples

Input 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

Output 1

2
8
9
105
7