Hirak Rajar Desh

Hirak Raja, the king of the country “Hirak Rajar Desh”, the conqueror ultimate, wanted to expand his kingdom. So, he decided to attack the Goopy kingdom. The Goopy kingdom consists of $n$ islands (numbered from 1 to $n$) and $n-1$ bridges. Each island has a leader with a leadership value $1 \leq L_i \leq 100$. Each bridge connects two different islands and it is possible to travel from any island to any other island within the Goopy kingdom using the bridges.

Hirak Raja wanted to conquer some islands from the Goopy kingdom. To conquer an island, Hirak Raja has to capture the leader of that island. Hirak Raja started his mission from island $u$. After conquering an island, he uses a bridge to move to another island that has not been conquered yet. He continues his mission for a while. After reaching island $v$, he stops and comes back to Hirak Rajar Desh with the captured leaders. Hirak Raja’s prison has $k$ cells in which he has to put those captured leaders. Each cell can contain an infinite amount of prisoners. He will put the leaders into cells in such a way that they cannot plan any conspiracy against him.

In cell $i$, if the maximum leadership value amongst leaders is $X_i$and the minimum is $Y_i$, then the probability that a conspiracy is forming within that cell is $P_i=(X_i-Y_i)/100$. The probability that Hirak Rajar Desh is in danger is: $\max\limits_{i=1, \, 2, \, \dots \, k}(P_i)$. That means the maximum of all $P_i \, (i=1,2,…,k)$. As Hirak Raja wants to save his throne, he will put the leaders in cells in such a way that the probability of his kingdom being in danger is minimized.

You have to answer $q$ different queries. Each query consists of 3 integers $u$, $v$, and $k$. You have to find out the probability that Hirak Rajar Desh is in danger if he started his attack from island $u$ and ended in island $v$ and there are $k$ cells in the prison.

Input

Input starts with two integers $n,q$ ($1 ≤ n\leq 10^6, 1\leq q \leq 2\times 10^5$) denoting the number of islands and number of queries to be answered.

The next $n-1$ lines contain $2$ integers $x, y \, (1≤ x, \, y≤ n)$ each, denoting there is a bridge between island $x$ and island $y$.

The next line contains $n$ integers, the leadership values $L_1, L_2,\dots,L_n$($1 \leq L_i \leq 100)$.

The next $q$ lines contain one query each. Each query consists of 3 integers $u$, $v$ and $k$($1\leq u,v \leq n ; 1\leq k \leq 100$ ) as described above.

Reminder: Dataset is huge. Please consider using faster I/O methods.

Output

For each query, print the probability that Hirak Raja’s kingdom is in danger. You have to print the probability in percentage. For example, if the probability is 0.37, you have to print 37%.

Sample

Input	Output
6 3 1 2 1 4 1 3 3 5 3 6 1 2 3 4 5 6 1 6 2 2 5 3 2 3 3	2% 1% 0%