Byteotian Software Corporation (BSC) 有 $n$ 名员工。在 BSC 严格的等级制度中，除了 CEO 之外，每位员工都有一位直接上级。所有其他员工直接或间接地向 CEO 汇报。每位员工的月薪都是唯一的，且都在 $1$ 到 $n$ 拜塔勒（bythalers）之间。每位上级的薪水都高于其所有下属。

根据 Byteotian 法律，某些岗位的员工薪水可以公开。此外，如果某位员工的薪水被公开，那么其上级的薪水也必须公开。

Byteotian 内部税务反腐败局 (BIRAS) 决定调查 BSC。在 BIRAS 持搜查令进入 BSC 之前，他们打算找出所有未公开但可以根据已公开薪水推断出的员工薪水。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示 BSC 的员工人数。员工的编号从 $1$ 到 $n$。

接下来的 $n$ 行提供了这些员工的信息。第 $i+1$ 行描述了编号为 $i$ 的员工，包含两个整数 $p_{i}$ 和 $z_{i}$ ($1 \le p_{i} \le n$, $0 \le z_{i} \le n$)，中间用空格隔开。$p_{i}$ 是员工 $i$ 的直接上级编号。如果 $p_{i}=i$，则 $i$ 是 BSC 的 CEO。如果 $z_{i} > 0$，则该值为员工 $i$ 的薪水。如果 $z_{i}=0$，则表示员工 $i$ 的薪水未公开。所有正数的 $z_{i}$ 互不相同。

输入数据保证至少存在一种符合等级制度和部分已知薪水分配的方案。

在总分 $54\%$ 的测试点中，满足 $n \le 10\,000$。

输出格式

程序应向标准输出打印 $n$ 行，每行包含一个整数。如果员工 $i$ 的薪水已公开或可以从已公开的薪水中推断出来，则第 $i$ 行应输出员工 $i$ 的薪水。否则，第 $i$ 行应输出 $0$。

样例

输入 1

10
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0

输出 1

2
10
1
9
5
8
0
0
0
0

该图展示了员工的等级结构。圆圈中的数字是员工编号，旁边的斜体数字（如果有）是他们已公开的薪水。员工 3 的薪水必须为 1 拜塔勒，员工 6 的薪水必须为 8 拜塔勒。员工 7、8、9 和 10 的薪水无法根据已公开的薪水唯一确定。