트리 경로의 k번째 작은 가중치

정점이 $N$개인 트리가 있다. 트리는 사이클이 없는 연결 무방향 그래프이다. 정점 번호는 1번부터 $N$번까지이고, 간선 번호는 1번부터 $N-1$번까지이다. 각 정점에는 가중치가 하나씩 붙어 있다.

다음 쿼리를 처리하는 프로그램을 작성하시오.

• u v k: 정점 $u$에서 정점 $v$로 가는 경로 위에 있는 정점의 가중치 중 $k$번째로 작은 값을 출력한다.

트리에서 두 정점을 잇는 경로는 하나뿐이고, 그 경로에는 양 끝 정점 $u$와 $v$도 포함된다. 같은 가중치가 여러 정점에 나오면 나온 횟수만큼 따로 세어 순위를 매긴다. 예를 들어 경로 위의 가중치가 3, 7, 7, 9라면 2번째로 작은 값과 3번째로 작은 값은 모두 7이다.

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

둘째 줄에 1번 정점부터 $N$번 정점까지의 가중치가 순서대로 주어진다. 가중치는 $1{,}000{,}000$보다 작거나 같은 자연수이다.

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

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

다음 $M$개의 줄에 쿼리가 한 줄에 하나씩 u v k 형식으로 주어진다. $u$와 $v$는 정점 번호이고 서로 같아도 된다. $k$는 $u$에서 $v$로 가는 경로 위의 정점 개수보다 크지 않은 자연수이다.

각 쿼리의 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.