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

시간 제한1.5초메모리 제한512 MB

요약

가중 트리에서 두 정점 사이 경로에 있는 정점 가중치 중 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개로 본다.

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

예제 4

입력

5 6
-2147483648 2147483647 0 -1 1
1 2
2 3
3 4
4 5
1 5 1
1 5 5
1 5 3
2 4 2
3 3 1
5 1 2

예상 출력

-2147483648
2147483647
0
0
0
-1

예제 5

입력

6 7
10 60 20 50 30 40
1 2
1 3
1 4
1 5
1 6
2 3 1
2 3 2
2 3 3
4 6 2
5 5 1
2 2 1
6 4 3

예상 출력

예제 6

입력

10 12
7 3 9 1 5 8 2 6 10 4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10 1
1 10 10
1 10 5
4 7 1
4 7 4
7 4 2
10 1 7
3 3 1
2 9 3
9 2 8
5 6 2
1 2 2

예상 출력