There are n cities and n − 1 roads, which are trees. Cities are numbered from 1 to n. When city 1 is taken as the root, the parent of city i is pi, and the distance between i and pi is di. Sunuke wants to solve the following problem for each k of 1 or more and n or less.

Minimum value of the sum of the distances from a city to cities 1, .. .., k \ begin {eqnarray} min_ {1 \ leq v \ leq n} \\ {\ sum ^ k_ {i = 1} dist (i) , v) \\} \; \; \; \; \; \; \; \; \; \; \; \; \; \; (2) \ end {eqnarray}

Find. However, dist (u, v) represents the distance between u and v.

Constraints

* 1 ≤ n ≤ 200000
* 1 ≤ pi ≤ n
* 1 ≤ di ≤ 200000
* The graph represented by pi is a tree
* All inputs are integers

Input


n
p2 d2
.. ..
pn dn


Output

Output n lines. On line i, output the answer when k = i.

Examples

Input

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


Output

0
3
3
4
5
7
10
13
16
19


Input

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


Output

0
3
9
13
14
21
22
29
31
37
41
41
47
56
59
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <complex>
 
using namespace std;
typedef long long ll;
 
/**
 * Link-Cut Tree
 *
 * ?????????¨????????????link???cut???evert???parent, root????????£???????
 * ??????????????????????????????´??????????????????
 */
struct LCNode {
    using NP = LCNode*;
 
    ll tsz, tszsm;
    ll tsm;
    ll d;
    ll dsm;
    ll lsm, rsm;
    LCNode() {}
    LCNode(int d) : p(nullptr), l(nullptr), r(nullptr), sz(1), rev(false) {
        tsz = 0;
        tszsm = 0;
        tsm = 0;
        this->d = d;
        dsm = d;
        lsm = rsm = 0;
    }
 
    void update() {
        int lsz = (l) ? l->sz : 0, rsz = (r) ? r->sz : 0;
        sz = 1;
        tszsm = tsz;
        dsm = d;
        if (lsz) {
            dsm += l->dsm;
            sz += lsz;
            tszsm += l->tszsm;
        }
        if (rsz) {
            dsm += r->dsm;
            sz += rsz;
            tszsm += r->tszsm;
        }
        ll ldsm = (l) ? l->dsm : 0;
        ll llsm = (l) ? l->lsm : 0;
        ll lrsm = (l) ? l->rsm : 0;
        ll ltszsm = (l) ? l->tszsm : 0;
        ll rdsm = (r) ? r->dsm : 0;
        ll rlsm = (r) ? r->lsm : 0;
        ll rrsm = (r) ? r->rsm : 0;
        ll rtszsm = (r) ? r->tszsm : 0;
        lsm = llsm + ldsm * tsz + tsm + (ldsm + d) * rtszsm + rlsm;
        rsm = rrsm + rdsm * tsz + tsm + (rdsm + d) * ltszsm + lrsm;
    }
    void cngchsz(int x) {
        tsz += x;
        tszsm += x;
    }
    void addch(NP b) {
        assert(!b || b->p == this);
        if (b) {
            cngchsz(b->tszsm);
            tsm += b->lsm + (d) * b->tszsm;
//          assert(!d);
        }
    }
    void delch(NP b) {
        assert(!b || b->p == this);
        if (b) {
            cngchsz(-b->tszsm);
            tsm -= b->lsm + (d) * b->tszsm;
//          assert(!d);
        }
    }
    void push() {
        int lsz = (l) ? l->sz : 0, rsz = (r) ? r->sz : 0;
        if (rev) {
            if (lsz) {
                l->revdata();
            }
            if (rsz) {
                r->revdata();
            }
            rev = false;
        }
    }
    void revdata() {
        swap(l, r);
        swap(lsm, rsm);
        rev ^= true;
    }
 
    //????????????
    NP p, l, r;
    int sz;
    bool rev;
    inline int pos() {
        if (p) {
            if (p->l == this) return -1;
            if (p->r == this) return 1;
        }
        return 0;
    }
    void rot() {
        NP q = p->p;
        int pps = p->pos();
        if (pps == -1) {
            q->l = this;
        }
        if (pps == 1) {
            q->r = this;
        }
        if (p->l == this) {
            p->l = r;
            if (r) r->p = p;
            r = p;
        } else {
            p->r = l;
            if (l) l->p = p;
            l = p;
        }
        p->p = this;
        p->update();
        update();
        p = q;
        if (q) q->update();
    }
    void splay() {
        supush();
        int ps;
        while ((ps = pos())) {
            int pps = p->pos();
            if (!pps) {
                rot();
            } else if (ps == pps) {
                p->rot(); rot();
            } else {
                rot(); rot();
            }
        }
    }
    void expose() {
        for (NP u = this; u; u = u->p) {
            u->splay();
        }
        for (NP u = this, ur = nullptr; u; u = u->p) {
            NP tmp = u->r;
            u->r = nullptr;
            u->update();
            u->addch(tmp);
            u->delch(ur);
            u->r = ur;
            u->update();
            ur = u;
        }
        splay();
    }
    void supush() {
        if (pos()) {
            p->supush();
        }
        push();
    }
    //????????????§??????¶?????????
 
    void link(NP r) {
        expose();
        r->expose();
        p = r;
        r->addch(this);
    }
 
    NP parent() {
        expose();
        NP u = this->l;
        if (!u) return nullptr;
        u->push();
        while (u->r) {
            u = u->r;
            u->push();
        }
        u->expose();
        return u;
    }
 
    void cut() {
        NP u = parent();
        assert(u);
        assert(!u->r);
        u->delch(this);
        this->p = nullptr;
    }
 
    NP root() {
        expose();
        NP u = this;
        while (u->l) {
            u = u->l;
            u->push();
        }
        u->expose();
        return u;
    }
 
    void evert() {
        expose();
        revdata();
    }
 
    NP lca(NP n) {
        n->expose();
        expose();
        NP t = n;
        while (n->p != nullptr) {
            if (!n->pos()) t = n->p;
            n = n->p;
        }
        return (this == n) ? t : nullptr;
    }
 
    NP get(int x) {
        push();
        int rszsm = (r) ? r->tszsm : 0;
        if (r && x <= rszsm) return r->get(x);
        if (x <= tsz + rszsm) {
            splay();
            return this;
        }
        if (l) return l->get(x - (tsz + rszsm));
        return nullptr;
    }
};
 
const int MN = 200200;
 
LCNode tr[MN], et[MN];
int p[MN];
int main() {
    int n;
    scanf("%d", &n);
    tr[0] = LCNode(0);
    for (int i = 1; i < n; i++) {
        int d;
        scanf("%d %d", p+i, &d); p[i]--;
        tr[i] = LCNode(0);
        et[i] = LCNode(d);
    }
    for (int i = 1; i < n; i++) {
        tr[i].link(et + i);
        et[i].link(tr + p[i]);
    }
 
    int sp = 0;
    printf("%d\n", 0);
    tr[0].expose();
    tr[0].cngchsz(1);
    for (int i = 1; i < n; i++) {
        tr[i].evert();
        tr[i].expose();
        tr[i].cngchsz(1);
        tr[sp].expose();
        sp = tr[sp].get(i/2+1) - tr;
        tr[sp].evert();
        tr[sp].expose();
        printf("%lld\n", tr[sp].lsm);
    }
    return 0;
}
 
 