题目描述

供水系统由 $N$ 个水站和 $N-1$ 条双向管道组成，形成一棵以水站 $1$ 为根的树。开始时，每个水站的水压均为 $0$。

共有 $Q$ 次操作。第 $j$ 次操作给出 $P_j$ 和 $X_j$，将以水站 $P_j$ 为根的子树中所有水站的水压增加 $X_j$。

请输出全部操作结束后每个水站的水压。

输入格式

第一行包含两个整数 $N,Q$。

接下来 $N-1$ 行，每行包含两个整数 $U_i,V_i$，表示水站 $U_i$ 和 $V_i$ 之间有一条管道。

接下来 $Q$ 行，每行包含两个整数 $P_j,X_j$，表示一次操作。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示水站 $i$ 的最终水压。数字之间用一个空格分隔。

样例

5 3
1 2
1 3
2 4
3 5
2 15
1 20
4 30

20 35 20 65 20

数据范围与提示

• $2 \le N \le 2\times10^5$
• $1 \le Q \le 2\times10^5$
• $1 \le U_i,V_i,P_j \le N$
• $1 \le X_j \le 10^4$
• 输入的管道保证构成一棵树