Boring tree queries

Given a tree with $n$ vertices. Each vertex of the tree has a single number written on it.

In this problem you must answer $q$ queries. Each query is described by three numbers $u$, $v$ and $k$. To answer the query, first write down the numbers written on the vertices in a simple path from $u$ to $v$ in the order they appear. Then the answer to the query is calculated in this way: add the first $k$ numbers of the obtained sequence, subtract the next $k$ numbers, then again add the next $k$ numbers, and then again subtract the next $k$ numbers, and so on. It is guaranteed that the number of vertices in a simple path from $u$ to $v$ is divisible by $k$.

Input

The first line contains two integers $n(1\le n\le 10^5)$ - the number of vertices in the tree, and $q(1\le q\le 10^5)$ — the number of queries.

The second line contains a sequence of $n$ integers $a_1,a_2,\dots ,a_n(1\le a_i\le 10000)$ — the numbers written on vertices.

Then follow $n-1$ lines, describing the tree edges. Each line contains a pair of integers $x_i,y_i(1\le x_i,y_i\le n,x_i\ne y_i)$ — the vertices connected by an edge.

The last $q$ lines describe the queries, the $i$-th line contains three numbers $u_i,v_i,k_i(1\le u_i,v_i,k_i\le n)$.

Output

Output $q$ lines, $i$-th line contains the answer to the $i$-th query.

Examples