题目描述

fateice 来到了魔方俱乐部旅行。

魔方俱乐部有 $N$ 个分部，每个分部均有且仅有一个虫洞，但是这虫洞只能通往一个分部。

每个分部有一个 orzFang 价值，第 $i$ 个分部的 orzFang 价值为 $A_i$。

现在他想知道，从第 $i$ 个分部出发，并只通过虫洞前往下一个分部，orzFang 价值之和最多是多少（到达一个分部多次只计算 $1$ 次 orzFang 价值）。

输入格式

第一行为一个正整数 $N$。

第二行有 $N$ 个非负整数 $A_i$，表示了每个分部的 orzFang 价值。

第三行有 $N$ 个正整数 $F_i$，表示通过第 $i$ 个分部的虫洞所到达的分部为 $F_i$，可能出现 $F_i=i$ 的情况。

输出格式

包括 $N$ 行，第 $i$ 行包含一个非负整数，表示从第 $i$ 个分部出发，orzFang 价值之和的最大值为多少。

样例

input

8
5 4 3 2 1 1 1 1
2 3 1 1 2 7 6 8

output

12
12
12
14
13
2
2
1

数据范围与提示

对于 $20\%$ 的数据，$N\le 10$。

对于 $40\%$ 的数据，$N\le 1000$。

对于 $100\%$ 的数据，$1\le N\le 2\times 10^5，1\le A_i\le 10^4$。