There are $n$ nodes, where the $x$-th node has a weight $a_x$. There are two trees that connect these $n$ nodes independently, and the node weights are shared between the two trees.

You need to perform $m$ operations. Each operation is given by $x, y, k$, and consists of the following two steps:

1. Increase the weights of all nodes on the shortest path between $x$ and $y$ in the first tree by $k$.
2. Calculate the sum of weights of all nodes on the shortest path between $x$ and $y$ in the second tree, modulo $2^{64}$.

Input

The first line contains two integers $n$ and $m$, representing the number of nodes and the number of operations.

The second line contains $n$ integers, where the $x$-th integer represents $a_x$, the initial weight of node $x$.

The next $n-1$ lines each contain two integers $x, y$, representing an edge between node $x$ and node $y$ in the first tree.

The next $n-1$ lines each contain two integers $x, y$, representing an edge between node $x$ and node $y$ in the second tree.

The next $m$ lines each contain three integers $x, y, k$, representing an operation.

Output

Output $m$ lines, each containing one integer representing the answer to each operation.

Examples

Input 1

3 2
1 10 100
2 3
3 1
1 3
3 2
2 3 1000
1 1 10000

Output 1

2110
10001

Input 2

5 7
0 3 2 6 4
1 2
2 4
1 5
5 3
3 4
4 2
2 5
5 1
5 3 0
3 2 5
4 4 4
4 4 3
5 2 0
3 4 3
5 5 6

Output 2

15
21
10
13
17
26
18

Constraints

• For all data, $1 \leq n, m \leq 2 \times 10^5$
• $0 \leq a_i, k < 2^{64}$
• $1 \leq x, y \leq n$

• Special Property A: The second tree is guaranteed to be generated uniformly at random among all unrooted trees with $n$ nodes.
• Special Property B: Both trees are guaranteed to be chains generated uniformly at random.
• Special Property C: For the first tree, when rooted at $1$, the parent of each node has a smaller index than the node itself, and the indices of nodes in each subtree are contiguous. For the second tree, the $x$-th edge connects node $x$ and node $x+1$.