某城市的供水系统由 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 说明

给定供水网络的结构如下：

    1
   / \
  2   3
 /     \
4       5

各水站（结点）初始水压均为 0。接下来的操作依次为：

• 第一阶段：选择水站 2，将水站 2 及其下属水站（水站 4）的水压各增加 15。

  • 水站 2：0 + 15 = 15。
  • 水站 4：0 + 15 = 15。
  • 其他节点保持 0。

• 第二阶段：选择水站 1，即：对整个供水系统所有水站水压增加 20。

  • 水站 1：0 + 20 = 20。
  • 水站 2：15 + 20 = 35。
  • 水站 3：0 + 20 = 20。
  • 水站 4：15 + 20 = 35。
  • 水站 5：0 + 20 = 20。

• 第三阶段：选择水站 4，仅对水站 4 增加 30 。

  • 水站 4：35 + 30 = 65。

最终各水站的水压为：

• 水站 1：20。
• 水站 2：35。
• 水站 3：20。
• 水站 4：65。
• 水站 5：20。

数据范围

对于 10\% 的数据，满足 P_j=1。

对于另外 10\% 的数据，满足 Q=1。

对于 60\% 的数据，满足 2 \leq N \leq 100，2 \leq Q \leq 100。

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