Bob is a renowned competitive programmer with a special interest in problems related to trees. When Alice challenged him to solve a question she had prepared, being the reputed programmer he is, he accepted without hesitation. Alice's question is described below:

You will be given a tree consisting of N nodes, with node 1 being the root. Each node is assigned a weight W. You will face multiple queries, where each query provides two nodes, U and V. Your task is to determine the difference between the sums of weights in the subtrees rooted at nodes U and V.

Bob easily tackled this question. Now, if you were in Bob's shoes, could you solve it too?

The first line contains two integers, N and Q, denoting the number of nodes in the tree and the number of queries, respectively.

The next line consists of N integers denoting the weights, W assigned to each node. 

The next N-1 lines contain two integers, A and B, representing an edge between nodes A and B.

Following that, there are Q lines, each containing two integers, U and V, representing the root for the sub-tree in each query.

1 ≤ N, Q, W ≤ 1e5
1 ≤ A, B, U, V ≤ N

For each query, output a single integer, containing the difference between the sum of the subtrees.

Input copy	Output copy
5 5 1 2 3 4 5 1 2 2 3 3 4 4 5 1 2 1 3 1 4 1 5 2 1	1 3 6 10 -1

For the first query, where U=1 & V=2. The sum of the subtree rooted at node 1, is 15. The sum of the subtree rooted at node 2, is 14. The difference between them is 15-14 = 1.

For the last query, where U=2 & V=1. The sum of the subtree rooted at node 1, is 15. The sum of the subtree rooted at node 2, is 14. The difference between them is 14-15 = -1.