트리 경로에서 K번째로 작은 수

1번부터 N번까지 번호가 붙은 N개의 정점과 N-1개의 간선으로 이루어진 트리가 있다. 각 정점에는 가중치가 하나씩 있다. 이 트리에 대해 M개의 질의를 주어진 순서대로 처리한다.

질의 X Y K는 정점 X와 정점 Y를 잇는 경로 위의 정점 가중치 중 K번째로 작은 값을 묻는다. 경로에는 양 끝 정점 X와 Y도 포함된다.

첫째 줄에 두 정수 N과 M이 주어진다. ($1 \le N, M \le 100\,000$)

둘째 줄에 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치다. 가중치는 모두 서로 다르고, 부호 있는 32비트 정수 범위에 들어간다.

다음 N-1개의 줄에는 각각 두 정수 X와 Y가 주어진다. 정점 X와 정점 Y가 간선으로 이어져 있다는 뜻이다.

다음 M개의 줄에는 각각 세 정수 X, Y, K가 주어진다. X와 Y는 1 이상 N 이하다. K는 1 이상이고, 정점 X와 정점 Y를 잇는 경로 위의 정점 개수 이하다. X와 Y가 같으면 그 경로 위의 정점은 1개로 본다.

질의마다 답을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.