Given a tree $T$ with $n$ vertices and $n-1$ weighted edges, initially, vertex $i$ is assigned color $i$ for $1 \leq i \leq n$. Since Marisa is dissatisfied with the structure of the tree $T$, she decides to shuffle the tree $T$ to obtain a new tree $T’$, where vertex $i$ will have the color $p_i$ ($1 \leq i \leq n$), and $p_1, p_2, \ldots, p_n$ is a permutation of $1, 2, \ldots, n$. After shuffling the tree $T$, Marisa provides $q$ queries. Each query $i$ consists of $u_i, v_i, x_i$. For the simple path from $u_i$ to $v_i$ in tree $T$, let the set of distinct colors on this path be $s_1, s_2, \ldots, s_k$. Compute the total distance from $x_i$ to every vertex with color $s_j$ in tree $T’$, for all $1 \leq j \leq k$.

Input

• The first line contains two positive integers $n$ and $q$.
• The second line contains $n$ positive integers $p_1, p_2, \ldots, p_n$.
• The next $n-1$ lines, the $i$-th line contains three positive integers $u_i, v_i, w_i$, describing an edge of the tree with weight $w_i$.
• The next $q$ lines, the $i$-th line contains three positive integers $u_i, v_i, x_i$.

Output

• Print $q$ lines, each containing the answer to the corresponding query.

Constraints

• $1 \le n,q \le 10^5.$
• $w_i \le 10^3.$

Example

Input

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

Output

5
7