問題文

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

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

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

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

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

制約

• $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)$

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

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

入力

$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$

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

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

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

出力

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

サンプル