问题陈述

我们有一棵具有 $N$ 个顶点和 $N-1$ 条边的树，其中顶点编号为 $1, 2, \\dots, N$，边的编号为 $1, 2, \\dots, N-1$。边 $i$ 连接顶点 $a_i$ 和 $b_i$。 树中的每个顶点上都写着一个整数。设 $c_i$ 表示顶点 $i$ 上写的整数。初始时，$c_i = 0$。

你将获得 $Q$ 个查询。第 $i$ 个查询由整数 $t_i$、$e_i$ 和 $x_i$ 组成，具体如下:

• 如果 $t_i = 1$：对于从顶点 $a_{e_i}$ 不经过顶点 $b_{e_i}$ 穿过边可达的每个顶点 $v$，将 $c_v$ 替换为 $c_v + x_i$。
• 如果 $t_i = 2$：对于从顶点 $b_{e_i}$ 不经过顶点 $a_{e_i}$ 穿过边可达的每个顶点 $v$，将 $c_v$ 替换为 $c_v + x_i$。

处理完所有查询后，打印每个顶点上写的整数。

约束条件

• 输入中的所有值都是整数。
• $2 \\le N \\le 2 \\times 10^5$
• $1 \\le a_i, b_i \\le N$
• 给定的图是一棵树。
• $1 \\le Q \\le 2 \\times 10^5$
• $t_i \\in \\{1, 2\\}$
• $1 \\le e_i \\le N-1$
• $1 \\le x_i \\le 10^9$

输入

输入以以下格式从标准输入给出:

$N$ $a_1$ $b_1$ $\\vdots$ $a_{N-1}$ $b_{N-1}$ $Q$ $t_1$ $e_1$ $x_1$ $\\vdots$ $t_Q$ $e_Q$ $x_Q$

输出

按照处理完所有查询后的顺序，每行打印 $c_1, c_2, \\dots, c_N$ 的值。

示例输入 1

5
1 2
2 3
2 4
4 5
4
1 1 1
1 4 10
2 1 100
2 2 1000

示例输出 1

11
110
1110
110
100

在第一个查询中，我们对从顶点 $1$ 可达而不经过顶点 $2$ 的每个顶点加上 $1$，即顶点 $1$。
在第二个查询中，我们对从顶点 $4$ 可达而不经过顶点 $5$ 的每个顶点加上 $10$，即顶点 $1, 2, 3, 4$。
在第三个查询中，我们对从顶点 $2$ 可达而不经过顶点 $1$ 的每个顶点加上 $100$，即顶点 $2, 3, 4, 5$。
在第四个查询中，我们对从顶点 $3$ 可达而不经过顶点 $2$ 的每个顶点加上 $1000$，即顶点 $3$。

示例输入 2

7
2 1
2 3
4 2
4 5
6 1
3 7
7
2 2 1
1 3 2
2 2 4
1 6 8
1 3 16
2 4 32
2 1 64

示例输出 2

72
8
13
26
58
72
5

示例输入 3

11
2 1
1 3
3 4
5 2
1 6
1 7
5 8
3 9
3 10
11 4
10
2 6 688
1 10 856
1 8 680
1 8 182
2 2 452
2 4 183
2 6 518
1 3 612
2 6 339
2 3 206

示例输出 3

1657
1657
2109
1703
1474
1657
3202
1474
1247
2109
2559