题目描述

给定一个根节点为1的有根树，具有$N$个从$1$到$N$编号的顶点。第$i$条边（$1 \leq i \leq N-1$）连接了顶点$a_i$和$b_i$。

每个顶点上都安装了一个计数器。初始时，所有顶点上的计数器的值都为$0$。

现在，将执行以下$Q$个操作：

• 操作$j$（$1 \leq j \leq Q$）：将以顶点$p_j$为根的子树中的每个顶点上的计数器增加$x_j$。

找出所有操作执行完后每个顶点上计数器的值。

约束条件

• $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$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入

输入以标准格式给出，格式如下：

$N$ $Q$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $p_1$ $x_1$ $:$ $p_Q$ $x_Q$

输出

按照顺序，以空格分隔打印所有操作执行完后每个顶点上计数器的值。

示例输入 1

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

示例输出 1

100 110 111 110

这个例子中的树结构如下：

每个操作都会改变顶点上计数器的值，如下所示：

• 操作 1：将以顶点 2 为根的子树中每个顶点上的计数器增加 10，即顶点 2、3、4。此时顶点上的计数器值为 0、10、10、10。
• 操作 2：将以顶点 1 为根的子树中每个顶点上的计数器增加 100，即顶点 1、2、3、4。此时顶点上的计数器值为 100、110、110、110。
• 操作 3：将以顶点 3 为根的子树中每个顶点上的计数器增加 1，即顶点 3。此时顶点上的计数器值为 100、110、111、110。

示例输入 2

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

示例输出 2

20 20 20 20 20 20