有 $n$ 个城市和 $n-1$ 条道路，它们构成一棵树。城市编号为 $1$ 到 $n$。城市 $1$ 是根节点，对于每个 $i$，城市 $i$ 的父节点是 $p_i$，且 $i$ 与 $p_i$ 之间的距离为 $d_i$。

Snuke 想要对每个 $1 \le k \le n$ 求解以下问题：

计算从某个城市到城市 $1, \dots, k$ 的距离之和的最小值：

$$\min_{1 \le v \le n} \left\{ \sum_{i=1}^{k} \text{dist}(i, v) \right\}$$

其中 $\text{dist}(u, v)$ 表示城市 $u$ 和 $v$ 之间的距离。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)。接下来 $n-1$ 行，第 $i$ 行包含两个整数 $p_{i+1}$ 和 $d_{i+1}$，分别表示城市 $i+1$ 的父节点以及城市 $i+1$ 与其父节点之间的距离 ($1 \le p_i \le n, 1 \le d_i \le 2 \cdot 10^5$，由 $p_i$ 表示的图是一棵树)。

输出格式

输出 $n$ 行。第 $i$ 行输出当 $k=i$ 时的答案。

样例

输入 1

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

输出 1

0
3
3
4
5
7
10
13
16
19

输入 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

输出 2

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