王昌龄参加了CSP的初赛却没能进入复赛，于是写下了著名的绝句《出塞》。

“胡马”指的是侵扰内地的外族骑兵。在古时候科技不发达，阻止骑兵行军的一种绝妙方式就是种树。如果树林非常茂密，骑兵就难以通行。

王昌龄亲手种下了一棵树，这棵树在缓慢的生长。第$1$天这棵树只有一个根节点，编号为$1$。此后的$n-1$天里，这棵树每天长出一个新的节点，按时间顺序编号为$2,3,\dots,n$。王昌龄非常关心这棵树的“大小”，也就是这棵树上最远的两个节点的距离。请你每天都向王昌龄汇报，今天树的“大小”是多少。

第一行一个整数$n$，表示总共有多少天。

接下来的$n-1$行中，第$i$行两个整数$f_i$和$d_i$，表示新长出的节点$i$的父亲节点时$f_i$，它与父亲节点的距离是$d_i$。

输出$n-1$行，每行一个整数，依次表示第$2,3,\dots,n$天树的“大小”。

样例说明
最终树的形态如下图所示

数据规模与约定
对于100%的数据，$2\leq n\leq2\times 10^5,\quad 0\leq d_i\leq10000$。