在一个神秘的魔法森林里，树木之间隐藏着古老的魔法力量。这片森林有N个魔法节点和N-1条魔法路径，这些节点分别编号为1到N，路径编号为1到N-1。第i条路径连接魔法节点a_{i}和b_{i}。每个魔法节点上最初都写着一个魔法能量值c_{i}=0。  

森林中的大法师会施放Q个魔法指令。第i个魔法指令包含整数t_{i}，e_{i}，和x_{i}，具体如下：

- 如果t_{i}=1：对于从魔法节点a_{e_{i}}出发，不经过魔法节点b_{e_{i}}而可以到达的所有节点v，将这些节点上的魔法能量值c_{v}增加x_{i}。

- 如果t_{i}=2：对于从魔法节点b_{e_{i}}出发，不经过魔法节点a_{e_{i}}而可以到达的所有节点v，将这些节点上的魔法能量值c_{v}增加x_{i}。

大法师施放完所有魔法指令后，请输出每个魔法节点上的最终能量值。

第一行包含一个正整数n  

接下来N-1行，每行两个正整数a_{i}和b_{i}。数据输入保证是一棵树。  

接下来一行一个正整数Q  

接下来Q行，每行三个正整数t_{i}，e_{i}，和x_{i}，具体如下：

- 如果t_{i}=1：对于从魔法节点a_{e_{i}}出发，不经过魔法节点b_{e_{i}}而可以到达的所有节点v，将这些节点上的魔法能量值c_{v}增加x_{i}。

- 如果t_{i}=2：对于从魔法节点b_{e}出发，不经过魔法节点a_{e_{i}}而可以到达的所有节点v，将这些节点上的魔法能量值c_{v}增加x_{i}。

输出一行n个空格隔开的整数，表示大法师施放完所有魔法指令后，每个魔法节点上的最终能量值。即输出c_{1} \sim  c_{n}

【数据范围与提示】

- 对于20%的数据，1 ≤n，Q ≤1000

- 另有20%的数据，1 ≤n ≤3500，1 ≤Q ≤2 ×10^{5}

- 对于100%的数据，1 ≤n，Q ≤2 ×10^{5}，1 ≤a_i, b_i ≤n，1 ≤e_i ≤n-1，1 ≤x_i ≤10^9