Orange的树上区间修改

题目描述

Orange有一颗 $n$ 个点构成的以 $1$ 为根节点的树，每个点均有一个点权，最开始均为0。现在Orange将会进行如下操作 $m$ 次：

1. 1 u x 给 $u$ 为根的子树每个点的点权加上 $x$。
2. 2 u v x 给 $u$ 和 $v$ 之间简单路径上的每个点的点权加上 $x$。

你的任务是，求出 $m$ 次操作后，每个节点的点权分别为多少。

输入格式

输入第一行为2个整数 $n,m$，表示树的大小与操作次数。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示存在一条连接 $u$ 和 $v$ 的边。 接下来 $m$ 行，每行一个操作，格式如上述。

数据范围

$1 \le n,m \le 2\times10^5$ $1 \le x \le 10^9$

输出格式

输出一个整数序列 $a_i$，$a_i$ 表示编号 $i$ 节点的点权。

样例 #1

样例输入 #1

2 2 3 2 3 3 2 38 4
1 2
1 3
1 4
3 5
5 6
4 7
3 8
1 3 1
1 1 1
2 2 7 1
2 6 8 1

样例输出 #1

2 2 3 2 3 3 2 3