問題文

頂点に 1 から N の番号がついた N 頂点 N 辺の有向グラフが与えられます。i 番目の辺は頂点 i から頂点 X_i への辺です。ただし、このグラフは辺の向きを無視した無向グラフにしたときに連結であることが保証されます。

各頂点にはいくつかの駒が置かれており、頂点 i には A_i 個の駒が置かれています。あなたはこれから以下の操作を N 回行います。

• すべての駒を、今置かれている頂点から出ている唯一の辺に沿って移動させる。

k = 0,1,\dots,N について、k 回目の操作が終わった時点での \sum_{i=1}^{N} (頂点 i に置かれている駒の個数) \times B_i を求めてください。

制約

• 1 \le N \le 2 \times 10^5
• 1 \le X_i \le N
• 1 \le A_i,B_i \le 10^6
• 与えられるグラフは辺の向きを無視した無向グラフにしたときに連結
• 入力はすべて整数

部分点

この問題には部分点が設定されている。

• X_i = i を満たす整数 i が存在するデータセットに正解した場合 1 点が与えられる。

入力例 1

3
2 1 1
4 1 2
3 5 1

出力例 1

19 29 27 29 

(頂点 1 に置かれている駒の個数 , 頂点 2 に置かれている駒の個数 , 頂点 3 に置かれている駒の個数) は、以下のように変化します。

• (4,1,2) \rightarrow (3,4,0) \rightarrow (4,3,0) \rightarrow (3,4,0)

それぞれの時点における \sum_{i=1}^{N} (頂点 i に置かれている駒の個数) \times B_i は、19,29,27,29 です。

入力例 2

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

出力例 2

59 66 60 68 76 76 76 

入力例 3

8
3 6 7 5 7 3 6 4
5 1 4 3 5 3 4 4
3 2 5 3 2 3 2 2

出力例 3

81 91 82 96 100 94 96 100 94 

入力例 4

10
2 6 9 5 9 5 6 2 6 6
23957 98539 98777 93417 64636 90740 72538 91432 11805 87997
6580 77845 27752 98108 4695 96373 76155 26842 12878 83118

出力例 4

44227480465 38056928301 30512335897 22545117713 30560451138 30512335897 22545117713 30560451138 30512335897 22545117713 30560451138