题目描述

给定一棵大小为 $n$ 的树。树上节点编号从 $1$ 到 $n$。

初始时每个节点都有一个点权，第 $i$ 个节点初始的权值为 $a_i(-1000 \le a_i \le 1000)$。

然后有 $m$ 次操作，每次操作给你三个整数 $x_i, y_i, z_i$，你需要将以节点 $x_i$ 为起点，以节点 $y_i$ 为终点的简单路径上所有点（包括节点 $x_i$ 和 $y_i$）的点权加上 $z_i$（$1 \le x_i, y_i \le n, -1000 \le z_i \le 1000$）。

在 $m$ 次操作结束后，请你输出树上每个节点的点权。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \times 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(-1000 \le a_i \le 1000)$，表示每个节点初始的权值。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示树上一条边连接的两个节点编号（$1 \le u_i, v_i \le n, u_i \neq v_i$）。

接下来一行，包含一个整数 $m(1 \le m \le 2 \times 10^5)$。

接下来 $m$ 行，每行包含三个整数 $x_i, y_i, z_i$，表示一次操作（$1 \le x_i, y_i \le n, -1000 \le z_i \le 1000$）。

输出格式

输出共一行，包含 $n$ 个整数，两两之间以一个空格分隔。其中第 $i$ 个整数表示最终节点 $i$ 的权值。

样例

6
1 2 3 4 5 6
1 2
2 3
2 4
4 5
4 6
3
1 3 1
3 5 2
2 6 3

2 8 6 9 7 9

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 20$
• 对于 $60\%$ 的数据，$n,m \le 2000$
• 对于 $100\%$ 的数据，$1 \le n,m \le 2 \times 10^5$