【题目描述】

小 Y 要去参加 NOIP，但是经验不足的他只会顺序开题。不仅如此，他还希望题目难度是升序的。

NOIP 有 $n$ 道题，第 $i$ 题的难度为 $i$，分数为 $c_i$，保证 $c_i\le c_{i+1}$。小 Y 将以某种顺序思考每道题恰好一次，第 $i$ 次将会思考第 $a_i$ 道题，$a_i$ 互不相同。

小 Y 会记录自己完成了的题目中难度最大值 $t$，初始 $t=0$。如果当前思考的题目为 $x$ 且 $x>t$，那么他就会完成该题，得到 $c_x$ 分，并更新 $t=x$。否则小 Y 是不屑于去做这道题的。

显然，当确定序列 $a$ 后，容易计算出小 Y 能得几分。于是你想解决更加困难的问题：有若干 $a_i=-1$（不确定是哪道题），考虑所有把 $-1$ 替换成 $1\sim n$ 的整数，仍保证 $a_i$ 互不相同的方案。对于 $k=1\sim n$，分别求出思考了 $k$ 道题后，小 Y 的最大得分。

【输入格式】

从文件 noip.in 中读入数据。

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

第二行 $n$ 个整数表示序列 $a$。

第三行 $n$ 个正整数表示序列 $c_i$。

【输出格式】

输出到文件 noip.out 中。

一行 $n$ 个正整数，第 $i$ 个表示当 $k=i$ 时的答案。

【样例 1 输入】

5
-1 -1 -1 -1 -1
1 1 1 1 1

【样例 1 输出】

1 2 3 4 5

【样例 2 输入】

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

【样例 2 输出】

3 4 7 9 9

【数据范围】

大样例