Problem Statement

There is a tree with $N$ vertices numbered $1\sim N$, rooted at vertex $1$.

The $i$-th edge $(1≤i≤N-1)$ connects vertices $a_i$ and $b_i$.

The cost of each vertex is initially $0$.

You are given $Q$ queries. In the $j$-th query, perform the following operation. For each query, output the sum of the costs of all vertices in the tree.

• Add $x_j$ to the cost of every vertex contained in the subtree rooted at vertex $p_j$. $(1≤j≤Q)$

Constraints

• $2≤N≤10^5$

• $1≤Q≤10^5$

• $1≤a_i,b_i,p_j≤N$ $(1≤i≤N-1,1≤j≤Q)$

• $1≤x_j≤10^8$ $(1≤j≤Q)$

• All inputs are integers.

• The given graph is a tree.

Input

$N$ $Q$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
$p_1$ $x_1$
$p_2$ $x_2$
$\vdots$
$p_Q$ $x_Q$

• The $1$st line contains $N$ and $Q$, separated by a space.

• Lines $2$ through $N$ contain $a_i$ and $b_i$ $(1≤i≤N-1)$, separated by a space.

• Lines $N+1$ through $N+Q$ contain $p_j$ and $x_j$ $(1≤j≤Q)$, separated by a space.

Output

Output the answers to the queries in $Q$ lines. Print a newline at the end.

Sample

3 1
1 2
1 3
1 5

15

10 5
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
8 10
8 100
4 200
5 100
3 200
2 100

200
1000
1100
1700
2300