在一个神秘的魔法森林里，树木之间隐藏着古老的魔法力量。这片森林有 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，含义如上。

输出一行 N 个空格隔开的整数，表示每个节点的最终能量值，即 c_1 \sim c_N。

样例 1 解释

树的形态为 1-2, 2-3, 2-4, 4-5。四个指令依次是：

• t=1, e=1, x=1：边 1 是 (1,2)，从 1 出发不经过 2 只能到 1 自己，节点 1 加 1；
• t=1, e=4, x=10：边 4 是 (4,5)，从 4 出发不经过 5 可以到 1,2,3,4，这四个节点各加 10；
• t=2, e=1, x=100：从 2 出发不经过 1 可以到 2,3,4,5，这四个节点各加 100；
• t=2, e=2, x=1000：边 2 是 (2,3)，从 3 出发不经过 2 只能到 3 自己，节点 3 加 1000。

最终 c = [11, 110, 1110, 110, 100]。

数据范围

• 对于 20\% 的数据，1 \le n, Q \le 1000；
• 另有 20\% 的数据，1 \le n \le 1000，1 \le Q \le 2 \times 10^5；
• 对于 100\% 的数据，1 \le n, Q \le 2 \times 10^5，1 \le e_i \le n-1，1 \le x_i \le 10^9。

提示

以 1 为根。删掉一条边后，两侧分别是一个子树和「整棵树减去这个子树」。注意这里只有最后统一输出一次查询，没有中途询问，所以可以用树上差分：设 d_v 表示「节点 v 相对它父亲的增量」，给子树加就 d_v \mathrel{+}= x，给「子树之外的全部」加就 d_1 \mathrel{+}= x,\ d_v \mathrel{-}= x，最后从根往下做一次前缀和即可，复杂度 O(n + Q)。

小提醒：N 可达 2 \times 10^5，链状数据下递归 dfs 容易爆栈，建议用 BFS 或手写栈求父子关系。