問題文

$N$ 頂点の木が与えられます。 $i = 1, 2, \dots, N-1$ について $i$ 番目の辺は頂点 $u_i$ と 頂点 $v_i$ を結んでいます。

また、長さ $N-1$ の正整数列 $A, B$ が与えられます。

次のような $N$ 頂点の有向グラフ $G$ を考えます。

• $i = 1, 2, \dots, N-1$ について、頂点 $u_i$ から頂点 $v_i$ に重み $A_i$ の辺を張る
• $i = 1, 2, \dots, N-1$ について、頂点 $v_i$ から頂点 $u_i$ に重み $B_i$ の辺を張る

$v = 1, 2, \dots, N$ について、頂点 $v$ を根とする最小有向全域木の重みを求めてください。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N \ (i = 1, 2, \dots, N-1)$
• $1 \leq A_i, B_i \leq 10^9 \ ( i = 1, 2, \dots, N-1)$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

出力

$v = 1, 2, \dots, N$ について、頂点 $v$ を根とする最小有向全域木の重みを空白区切りで出力してください。

例

3
1 2 5 7
1 3 4 8

9 11 13

例えば、頂点 $1$ を根とする最小有向全域木の重みは $5 + 4 = 9$ です。

出力する値が 32bit 整数型に収まらないことがあることに注意してください。