题目描述

有一棵包含 ( n ) 个结点（结点编号为 ( 1 到 n）的树。初始时，每个结点的权值均为 ( 0 ) 。随后会进行 ( q ) 次操作，每次操作选择一个结点 ( x )，将 ( x ) 以及 ( x ) 的所有子结点的权值增加 ( k ) 。请在完成所有操作后，输出每个结点最终的权值。

输入格式

第一行包含两个整数 ( n )（ $1 <= 10^5$ ）和 ( q )( $1<=q<=10^5$ ），分别表示树的结点数量和操作次数。

接下来 ( n - 1 ) 行，每行包含两个整数 ( x ) 和 ( y )，表示结点 ( x ) 和结点 ( y ) 之间有一条边（树的结构需自行构建，默认以 ( 1 ) 号结点为根，通过遍历确定父子关系）。

再接下来 ( q ) 行，每行包含两个整数 ( x ) 和 ( k )，表示对结点 ( x ) 及其所有子结点执行权值增加 ( k ) 的操作。

输出格式

输出 ( n ) 个数字，第 ( i ) 个数字输出结点 ( i ) 最终的权值。

样例输入 #1

5 3
1 2
1 3
2 4
2 5
2 3
2 3
2 3

输出样例 #1

0 9 0 9 9