K-th smallest weight on a tree path

Time limit1.5sMemory limit512 MB

Summary

Answer each query with the K-th smallest vertex weight on the path between two vertices in a tree.

Level: Hard8 of 10
Topics: Segment tree, Tree, Sorting
Solved: No attempts yet

Problem

A tree has N vertices numbered 1 to N and N-1 edges. Each vertex carries one weight. Process M queries on this tree in the order they are given.

A query X Y K asks for the K-th smallest weight among the vertices on the path between vertex X and vertex Y. The path includes both endpoints X and Y.

Input

The first line has two integers N and M. ( $1 \le N, M \le 100\,000$ )

The second line has N integers, the weights of the vertices. The i-th integer is the weight of vertex i. All weights are different, and each one fits in a signed 32-bit integer.

Each of the next N-1 lines has two integers X and Y, meaning vertex X and vertex Y are joined by an edge.

Each of the next M lines has three integers X, Y, and K. X and Y are between 1 and N. K is at least 1 and at most the number of vertices on the path between vertex X and vertex Y. If X and Y are the same, that path holds 1 vertex.

Output

Print one answer per query on its own line, in the order the queries are given.

Examples6

Example 1
Input
```
3 2
1 2 3
1 2
3 1
2 3 1
1 3 2
```
Expected output
```
1
3
```
Example 2
Input
```
1 3
42
1 1 1
1 1 1
1 1 1
```
Expected output
```
42
42
42
```
Example 3
Input
```
2 3
-5 7
2 1
1 2 1
1 2 2
2 2 1
```
Expected output
```
-5
7
7
```

Example 4

Input

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

Expected output

-2147483648
2147483647
0
0
0
-1

Example 5

Input

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

Expected output

Example 6

Input

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

Expected output