Description

学校不久前买了第$1$台计算机（编号为$1$）。近年来，学校又买了$N-1$台新计算机。每台新计算机都被连接到先前安装的一台计算机上。学校管理者担心网络运行缓慢，想知道第i台计算机发送信号的最大距离$s_i$（即电缆到最远的计算机的长度）。

提示：输入样例对应上图，可以看出，计算机$1$距离$4$最远，最远电缆长度为$3$，所以$s_1=3$。计算机$2$距离$5$和$4$最远，最远电缆长度$s_2=2$。计算机$3$距离$5$最远，最远电缆长度$s_3=3$。同理，得到$s_4=4$、$s_5=4$。

Format

Input

输入包含多个测试用例。每个测试用例的第1行都为$n（n≤10000）$，后面$n-1$行为对计算机的描述。第i行包含两个自然数，分别表示连接第$i$台计算机的计算机编号和用于连接的电缆长度。电缆总长度不超过$109$。

Output

对每个测试用例，都输出$n$行，第$i$行表示第$i$台计算机到其他计算机的最远距离。对每个测试用例，都输出$n$行，第$i$行表示第$i$台计算机到其他计算机的最远距离。

Samples

5
1 1
2 1
3 1
1 1

3
2
3
4
4