Description

$\hspace{15pt}$就在10月24日的晚上，帽子学长得到了一棵有 $n$ 个节点的树，节点编号为 1 到 $n$，每条边有一个正整数的权值 $w$。每个节点 $i$ 有一个点权 $a_i$。

$\hspace{15pt}$定义函数 $f(i, j)$ 表示从节点 $i$ 到节点 $j$ 的路径上所有边权的总和；定义以节点 $i$ 为根的树的权值 $R_i$ 为：

$$R_i = \sum_{1\leq j \leq n,\,j\neq i} a[j] \times (-1) ^ {\,f(i, j)}$$

$\hspace{15pt}$请你分别求出以每个节点为根的树的权值。即求出所有 $R_i$ ($1\leq i \leq n$)。

Format

Input

$\hspace{15pt}$第一行一个整数 $n$，表示有 $n$ 个节点（ $1 \leq n \leq 10^5$ ）。

$\hspace{15pt}$接下来一行包含 $n$ 个整数，第 $i$ 个数的值为 $a_i$ $( -1000 \leq a_i \leq 1000 )$。

$\hspace{15pt}$接下来 $n-1$ 行，每行包含三个整数 $u ,\, v ,\,w$ ，表示节点 $u$ 和节点 $v$ 之间有一条权值为 $w$ 的边。 （ $1 \leq u,v \leq n , 1 \leq w \leq 10^6$）。

Output

$\hspace{15pt}$输出一行包含 $n$ 个整数，第 $i$ 个数表示以 $i$ 为根节点的树的权值。

Samples

3
1 2 3
1 2 1
2 3 2

-5 2 1