$N$개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있고, 간선은 $1$번부터 $N-1$번까지 번호가 매겨져 있다. 정점은 가중치를 가지고 있다.

아래의 쿼리를 수행하는 프로그램을 작성하시오.

• u v k: $u$에서 $v$로 가는 경로에 존재하는 정점의 가중치 중에서 $k$번째 작은 가중치를 출력한다.

입력

첫째 줄에 $N$ ($2 \le N \le 100{,}000$)이 주어진다.

둘째 줄에는 정점의 가중치가 $1$번 정점부터 순서대로 주어진다.

셋째 줄부터 $N-1$개의 줄에는 $i$번 간선이 연결하는 두 정점 번호 $u$와 $v$가 주어진다.

다음 줄에는 쿼리의 개수 $M$ ($1 \le M \le 100{,}000$)이 주어진다.

다음 $M$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

정점의 가중치는 항상 $1{,}000{,}000$보다 작거나 같은 자연수이다.

출력

각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

Sample

Input

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

2
8
9
105
7