题目描述

一所学校前一段时间买了第一台计算机（所以这台计算机的$\red {ID}$是$\red {1}$）。

近年来，学校又购买了$\red {N-1}$台新计算机。

每台新计算机都与之前买进的计算机中的一台建立连接。

现在请你求出第$\red i$台计算机到距离其最远的计算机的电缆长度。

例如，上图中距离计算机$\red {1}$最远的是计算机$\red {4}$，因此 $\red {S_1=3}$；距离计算机$\red {2}$最远的是计算机$\red {4}$和$\red {5}$，因此 $\red {S_2=2}$；距离计算机$\red {3}$最远的是计算机$\red {5}$，所以 $\red {S_3=3}$；同理，我们也得到 $\red {S_4=4，S_5=4}$。

输入格式

输入包含多测试数据。

每组测试数据第一行包含整数$\red {N}$。

接下来$\red {N-1}$行，每行包含两个整数，第 $\red {i }$行的第一个整数表示第 $\red {i}$ 台电脑买入时连接的电脑编号，第二个整数表示这次连接花费的电缆长度。

输出格式

每组测试数据输出$\red {N}$行。

第 $\red {i}$ 行输出第 $\red {i}$ 台电脑的$\red { S_i}$。

样例

输入样例

5
1 1
2 1
3 1
1 1

输出样例

3
2
3
4
4

提示

$\red {1≤N≤10000}$,

电缆总长度不超过$\red {10^9}$