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.
The first line contains two integers n (1≤n≤105) - the number of vertices in the tree, and q (1≤q≤105) — the number of queries.
The second line contains a sequence of n integers a1,a2,…,an (1≤ai≤10000) — the numbers written on vertices.
Then follow n−1 lines, describing the tree edges. Each line contains a pair of integers xi,yi (1≤xi,yi≤n,xi=yi) — the vertices connected by an edge.
The last q lines describe the queries, the i-th line contains three numbers ui,vi,ki (1≤ui,vi,ki≤n).
Output q lines, i-th line contains the answer to the i-th query.