Description

$lyx$正在游戏中创建自己的国家，她的国家初始只有一座城市(首都)，之后的每个回合会增加一座新城市以及一条连接新旧城市的道路，游戏中货物的运输速度由相距最远的两座城市之间的距离决定，因为$lyx$忙着计算运输货物的最大价值，所以她把计算每回合最远距离的任务交给了$ljh$，你能帮助$ljh$解决这个问题吗

初始只有 $0$ 号节点(首都)，第 $i$ 回合增加 $i$ 号节点(新增城市)及一条连接 $i$ 号节点和已经存在节点的道路，共 $n$ 回合,计算每回合相距最远的两座城市之间的距离

本题中两点距离为不经过重复道路的最短距离

Format

Input

每个测试点只有一组测试数据

第一行一个正整数 $n(1 \leq n \leq 1e3)$ 代表回合数

然后有 $n$ 行：

第 $i$ 行有两个用空格隔开的整数 $x(0 \leq x < i)$ 和 $y(1 \leq y \leq 1e5)$ ，代表第 $i$ 回合新增 $i$ 号节点，新增一条连接 $i$ 号节点和 $x$ 号节点的长度为 $y$ 的道路

Output

输出包括 $n$ 行：
第 $i$ 行一个正整数代表第 $i$ 回合相距最远的两座城市之间的距离

Samples

5
0 9
0 1
2 2
3 3
3 7

9
10
12
15
19