时空限制

1S/512M

题目描述

有 $n$ 个人参加一场接力赛，每个人的编号分别为 $1$ 到 $n$。

已知接力赛时，第 $i$ 个人的前一棒选手的编号是 $a_i$（当 $a_i = 0$ 时，表示第 $i$ 个人是第一棒起跑的选手）。同时，第 $i$ 个人跑完自己负责的路程需要花费 $t_i$ 秒的时间。

假设第一棒选手在第 $0$ 秒时刻起跑，交接棒不消耗时间。请你求出每名学生分别是在第几秒时刻接到接力棒并开始起跑的？

格式

输入格式

第一行包含一个正整数 $n$，表示参加接力赛的总人数。

第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示第 $i$ 个人的前一棒选手编号。

第三行包含 $n$ 个正整数 $t_1, t_2, \dots, t_n$，表示第 $i$ 个人跑完自己路程需要的时间。

输出格式

输出共一行，包含 $n$ 个整数，以空格隔开。其中第 $i$ 个整数表示编号为 $i$ 的学生接到接力棒并开始起跑的时刻（单位：秒）。

样例

样例输入 #1

4
3 4 0 1
2 1 5 3

样例输出 #1

5 10 0 7

样例解释 #1

• 编号为 3 的学生 $a_3 = 0$，是第一棒选手，起跑时刻为第 0 秒，用时 5 秒；
• 编号为 1 的学生 $a_1 = 3$，是第二棒选手，在编号 3 跑完时接到棒，起跑时刻为第 0 + 5 = 5 秒，用时 2 秒；
• 编号为 4 的学生 $a_4 = 1$，是第三棒选手，在编号 1 跑完时接到棒，起跑时刻为第 5 + 2 = 7 秒，用时 3 秒；
• 编号为 2 的学生 $a_2 = 4$，是第四棒选手，在编号 4 跑完时接到棒，起跑时刻为第 7 + 3 = 10 秒。

最终按照编号 $1$ 到 $n$ 的顺序，依次输出起跑时刻：5 10 0 7。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$0 \leq a_i \leq n$，$1 \leq t_i \leq 10^4$。 保证根据给出的信息，排列方式只有一种。