题目描述

你在超市里工作。

超市里有 $n$ 个水果，第 $i$ 个水果的美味度为 $i$ ，价格为 $c_i$ ，并且保证 $c_i$ 单调不降。

现在要把这 $n$ 个水果摆成一排放到货架上，第 $j$ 个位置摆的水果是 $a_j$ 。但是你还没想好摆的顺序，所以可能会有 $a_j=-1$ ，表示这个位置摆的水果未定。

在你决定了摆放顺序之后，一位顾客进来买水果。他会从第一个位置开始往后走，每当遇到一个美味度比之前都要高的水果时就会把它买下，直到看完第 $k$ 个位置后离开。

你希望选择一个最优的摆放顺序，使得这位顾客出的钱最多。

但是你并不知道 $k$ 是多少，因此你希望对每个 $k$ 都求出答案。你对不同的 $k$ 给出的顺序可以不同。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 。

第三行 $n$ 个正整数 $c_1,c_2,\cdots,c_n$ 。

输出格式

输出一行 $n$ 个正整数，表示 $k=1,2,\cdots,n$ 时的答案。

样例一

input

5
-1 3 -1 -1 -1
1 2 2 2 3

output

3 4 7 9 9

explanation

• $k=1$ 的最优方案是把第 $5$ 个水果放第一个位置，即令 $a_1=5$ ，后面任意。
• $k=2$ 的最优方案是令 $a_1=2$ 。
• $k=3$ 的最优方案是令 $a_1=2,a_3=5$ 。
• $k=4$ 的最优方案是令 $a_1=2,a_3=4,a_4=5$ 。
• $k=5$ 的最优方案是令 $a_1=2,a_3=4,a_4=5,a_5=1$ 。

样例二

input

13
-1 -1 5 6 -1 -1 7 11 -1 -1 10 -1 -1
1 1 1 1 1 1 1 1 1 1 1 1 1

output

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

样例三

input

10
-1 -1 -1 -1 5 -1 -1 -1 9 -1
5 11 24 27 35 60 72 81 91 92

output

92 173 245 305 305 332 356 367 406 498

样例四、五、六

见下发文件。

数据范围

本题采用子任务捆绑测试。

对于所有数据，保证 $1\le n\le 4\times 10^5, -1\le a_i\le n, a_i\ne 0, 1\le c_i\le 10^9$ ，$a$ 中不存在两个相同的正整数，$c$ 单调不降。

时间限制：$\texttt{3s}$

空间限制：$\texttt{1024MB}$

提示

pjudge 缺投。