問題文

$1\sim N$ の番号が付いた $N$ 頂点の、頂点 $1$ を根とする木があります。

$i$ 番目の辺 $(1\le i\le N-1)$ は 頂点 $a_i$ と $b_i$ を結びます。

また、各頂点のコストは $0$ で初期化されています。

クエリが $Q$ 個与えられ、$j$ 個目のクエリでは以下の操作をします。クエリごとに木の全頂点のコストの総和を答えてください。

• 頂点 $p_j$ を根とする部分木に含まれる全ての頂点のコストに $x_j$ を足す。 $(1\le j\le Q)$

制約

• $2\le N\le {10}^5$

• $1\le Q\le {10}^5$

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

• $1\le x_j\le {10}^8$ $(1\le j\le Q)$

• 入力は全て整数である。

• 与えられるグラフは木である。

入力

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

• $1$ 行目に $N$ と $Q$ が空白区切りで与えられる。

• $2$ 行目から $N$ 行目には、 $a_i$ と $b_i$ $(1\le i\le N-1)$ が空白区切りで与えられる。

• $N+1$ 行目から $N+Q$ 行目には、 $p_j$ と $x_j$ $(1\le j\le Q)$ が空白区切りで与えられる。

出力

クエリごとの答えを $Q$ 行出力してください。最後に改行してください。

サンプル

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