This world need more Zhu

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.

1
5 5
1 2 4 1 2
1 2
2 3
3 4
4 5
1 1 1
1 3 2
1 3 100
1 5 2
1 3 1

Case #1:
1
2
0
2
4

In query 1,there are only one vertex in the path,so the answer is 1.

In query 2,there are three vertices in the path.But only the vertex 2 mod 2 equals to 0.

In query 3,there are three vertices in the path.But no vertices mod 100 equal to 0.

In query 4,there are five vertices in the path.There are two vertices mod 2 equal to 0.So the answer is max(a[2],a[4]) = 2.

In query 5,there are three vertices in the path.And all the vertices mod 1 equal to 0. So the answer is a[3] = 4.

UESTC

2016中国大学生程序设计竞赛 - 网络选拔赛