You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.

\n

We will ask you to perform the following operation:

\n

u v k : ask for the kth minimum weight on the path from node u to node v

\n\n

Input

\n

In the first line there are two integers N and M. (N, M <= 100000)

\n

In the second line there are N integers. The ith integer denotes the weight of the ith node.

\n

In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).

\n

In the next M lines, each line contains three integers u v k, which means an operation asking for the kth minimum weight on the path from node u to node v.

\n\n

Output

\n

For each operation, print its result.

\n\n

Example

\n

Input:\n8 5\n105 2 9 3 8 5 7 7\n1 2\n1 3\n1 4\n3 5\n3 6\n3 7\n4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2

\n

Output:\n2
8
9
105
7

统计

递交统计

Count on a tree

信息

状态

开发

支持

还没有账户？

登录