As we all know, Zhu is the most powerful man. He has the infinite power to protest the world. We need more men like Zhu!
In Duoladuo, this place is like a tree. There are $n$ vertices and $n-1$ edges. And the root is $1$. Each vertex can reached by any other vertices. Each vertex has a people with value $A_i$ named Zhu's believer.
Liao is a curious baby, he has $m$ questions to ask Zhu. But now Zhu is busy, he wants you to help him answer Liao's questions.
Liao's question will be like "u v k".
That means Liao want to know the answer from following code:
ans = 0; cnt = 0;
for x in the shortest path from u to v {
cnt++;
if(cnt mod k == 0) ans = max(ans,a[x]);
}
print(ans).
Please read the hints for more details.
In the first line contains a single positive integer $T$, indicating number of test case.
In the second line there are two numbers $n$, $m$. $n$ is the size of Duoladuo, $m$ is the number of Liao's questions.
The next line contains $n$ integers $A_1, A_2, ...A_n$, means the value of ith vertex.
In the next $n-1$ line contains tow numbers $u$, $v$. It means there is an edge between vertex $u$ and vertex $v$.
The next $m$ lines will be the Liao's question:
u v k
$1 \leq T \leq 10,1 \leq n \leq 100000,1 \leq m \leq 100000,1 \leq u,v \leq n,1 \leq k,\ A_i \leq 1000000000$.
For each case, output Case #i: (i is the number of the test case, from 1 to $T$).
Then, you need to output the answer for every Liao's questions.