Count on a tree

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem

A tree has $N$ weighted vertices. Query $u,v,k$ asks for the $k$-th smallest vertex weight on the simple path from $u$ to $v$, including both endpoints.

Input

The first line contains $N,M$, then the vertex weights, $N-1$ edges, and finally $M$ queries $u,v,k$.

Output

Print the $k$-th smallest weight for each path query.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le N,M\le10^5$
• vertex weights are integers
• $1\le u,v\le N$
• $1\le k\le$ the number of vertices on path $u-v$

Example

Input

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2

Output

2
8
9
105
7

Explanation

Path 2-1-3-5 has weights [2,105,9,8], which sort to [2,8,9,105].