n 個の都市と n − 1 本の道路があり，木になっている．都市には 1 から n までの番号がつけられている．都市 1 を根とみたとき，都市 i の親は p_i であり，i と p_i の距離は d_i である．すぬけ君は，1 以上 n 以下の各 k に対し，次の問題を解きたい．

ある都市から都市 1, . . . . , k への距離の和の最小値 $$\begin{eqnarray} min_{1 \leq v \leq n} \{ \sum^k_{i=1} dist(i, v)\} \;\;\;\;\;\;\;\;\;\;\;\;\;\;(2) \end{eqnarray}$$

を求めよ．ただし dist(u, v) は u と v の距離をあらわす．

Constraints

• 1 ≤ n ≤ 200000
• 1 ≤ p_i ≤ n
• 1 ≤ d_i ≤ 200000
• p_i によって表されるグラフは木になっている
• 入力は全て整数である

Input

n
p2 d2
. . .
pn dn

Output

n 行出力せよ．i 行目には，k = i のときの答えを出力せよ．

Sample Input 1

10
4 1
1 1
3 1
3 1
5 1
6 1
6 1
8 1
4 1

Sample Output 1

0
3
3
4
5
7
10
13
16
19

Sample Input 2

15
1 3
12 5
5 2
12 1
7 5
5 1
6 1
12 1
11 1
12 4
1 1
5 5
10 4
1 2

Sample Output 2

0
3
9
13
14
21
22
29
31
37
41
41
47
56
59