小泽负责处理一棵树上的区域加分。树中共有 $N$ 个顶点，所有顶点的初始分数都是 $0$。树的 $N-1$ 条边按照输入顺序编号为 $1$ 到 $N-1$，第 $e$ 条边连接顶点 $a_e$ 和顶点 $b_e$。

现在有 $Q$ 次操作，每次操作给出三个整数 $t,e,x$。如果删除第 $e$ 条边，原树会分成两个连通部分：

• 当 $t=1$ 时，把删除这条边后仍能从顶点 $a_e$ 到达的所有顶点的分数都增加 $x$；
• 当 $t=2$ 时，把删除这条边后仍能从顶点 $b_e$ 到达的所有顶点的分数都增加 $x$。

请在完成全部操作后，输出每个顶点的最终分数。

输入格式

第一行输入一个整数 $N$，表示顶点数量。

接下来 $N-1$ 行，第 $e$ 行输入两个整数 $a_e$ 和 $b_e$，表示编号为 $e$ 的边。

随后输入一个整数 $Q$，表示操作次数。

接下来 $Q$ 行，每行输入三个整数 $t,e,x$，描述一次操作。

输出格式

输出 $N$ 行。第 $i$ 行输出一个整数，表示顶点 $i$ 的最终分数。

7
3 1
2 1
4 7
5 6
4 1
5 3
7
1 5 159746471
1 6 952413827
1 2 245253640
1 6 642026085
1 5 552085323
1 1 428065689
2 4 294378801

0
245253640
428065689
711831794
2022505601
2316884402
711831794

10
2 4
3 1
9 3
7 4
5 10
2 5
7 8
5 6
2 1
1
2 1 604729189

0
0
0
604729189
0
0
604729189
604729189
0
0

4
4 2
2 3
1 2
7
1 2 579820741
2 3 919582788
2 2 176938368
1 1 383349547
2 1 916589431
1 2 920999361
1 1 498604496

2417409533
3336992321
2013110587
3302356933

数据范围与约定

• $2\le N\le2\times10^5$
• $1\le Q\le2\times10^5$
• $1\le x\le10^9$
• 输入图是一棵树