当前没有测试数据。

题目描述

某城市的供水系统由 $N$ 个水站构成，各水站通过管道相连，形成了一棵以水站 $1$ 为根的树形结构。

为提高居民用水体验，市政工程师计划对供水系统进行升级。系统初始时各水站的水压均为 $0$。

升级工程分为 $Q$ 个阶段，第 $j$ 个阶段，工程师会选择一个水站 $P_j$，并对该水站及其所有下游水站（即以水站 $P_j$ 为根的子树中所有的水站）进行水压提升操作，使其水压增加 $X_j$。

请你协助工程师计算出经过所有升级阶段后，每个水站的最终水压值。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$，分别表示水站的数量和升级阶段的次数。

接下来的 $N − 1$ 行，每行包含两个整数 $U_i$ 和 $V_i$，表示水站 $U_i$ 和水站 $V_i$ 之间有一条管道连接（保证形成一棵以水站 $1$ 为根的树状结构）。

之后的 $Q$ 行，每行包含两个整数 $P_j$ 和 $X_j$，表示在一次升级中，将水站 $P_j$ 及其下游水站的水压各增加 $X_j$。

输出格式

输出一行，包含 $N$ 个整数，第 $i$ 个数表示水站 $i$ 在所有升级阶段后的最终水压值，各数值之间用空格隔开。

样例 #1

输入

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

输出

20 35 20 65 20

数据范围

对于 $100\%$ 的数据，满足 $2 \le N \le 2 \times 10^5$，$1 \le Q \le 2 \times 10^5$，$1 \le U_i, V_i \le N$，$1 \le P_j \le N$，$1 \le X_j \le 10^4$。