题目描述

给定一个有 $N$ 个节点(编号从$1$到 $N$)的有根树。 根节点是节点 $1$，第 $i$ 条边 $(1 <i< N - 1)$连接节点$a$ 和 $b$;。

每个节点上都安装了一个计数器。初始时，所有节点上的计数器的值为 $0$。现在，将进行以下 $Q$ 次操作:

• 操作 $j(1 \leq j \leq Q)$:将以节点 $p_j$为根的子树中的每个节点的计数器增加$x_j$。

求在所有操作完成后，每个节点上计数器的值。

输入

输入第一行两个整数$N,Q$

接下来一共$N$行，每行两个整数$a_i,b_i$

接下来一共$Q$行，每行两个整数$p_i,x_i$

输出

按顺序输出每个节点 $1,2,…,N$ 上计数器的值，并用空格分隔。

4 3
1 2
2 3
2 4
2 10
1 100
3 1

100 110 111 110

样例解释

该输入中的树如下图所示:

每次操作改变节点上计数器的值如下:

第 1次操作:将以节点2为根的子树中的每个节点的计数器增加 10，即节点 2,3,4的计数器值变为 10。节点1,2,3,4 的计数器值变为 0,10,10,10。

第2次操作:将以节点1为根的子树中的每个节点的计数器增加 100，即节点 1,2,3,4的计数器值变为 110。节点1,2,3,4 的计数器值变为 100,110,110.110。

第3次操作:将以节点3为根的子树中的每个节点的计数器增加 1，即节点3的计数器值变为 111。节点 1,2,3,4的计数器值变为 100,110,111,110。

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

20 20 20 20 20 20

提示

$2 \leq N \leq 2 \times 10^5$

$1 \leq Q \leq 2 \times 10^5$

$1 \leq a_i< b_i \leq N$

$1 \leq p_j \leq N$

$1 \leq x_j \leq 10^4$

给定的图是一颗树