超市通常在不同的区域售卖水果，每个区域专门售卖一种水果。Benson 兔子正在参观的超市有 $N$ 个区域和 $N$ 种水果。区域编号为 $1$ 到 $N$，每种水果的编号也为 $1$ 到 $N$。

第 $i$ 种水果的美味度为 $i$，成本为 $C_i$。保证对于所有 $1 \le i < j \le N$，都有 $C_i \le C_j$。

每个区域将被分配一种不同的水果。目前，分配给区域 $j$ 的水果类型为 $A_j$。如果 $A_j = -1$，则表示区域 $j$ 为空。否则，水果 $A_j$ 已经被分配给区域 $j$。一旦所有 $N$ 种水果都被分配完毕，超市就会开门，Benson 将进入超市购买水果。

Benson 非常挑剔且时间紧迫，因此他会按编号递增的顺序参观各个区域。Benson 的篮子最初是空的，当他到达一个区域时，他会将该区域水果的美味度与他篮子中所有水果的美味度进行比较。如果他的篮子是空的，或者当前区域水果的美味度大于他篮子中所有其他水果的美味度，Benson 就会将该水果放入篮子中。

为了最大化收益，你需要将水果分配到各个区域，使得 Benson 加入篮子的水果的成本之和最大化。由于 Benson 时间紧迫，他可能只参观前几个区域就直接去收银台了。请帮助计算，对于每个 $k$（从 $1$ 到 $N$），如果 Benson 只参观前 $k$ 个区域，在水果排列方式可以针对不同 $k$ 进行调整的情况下，他能获得的最大收益。

输入格式

程序必须从标准输入读取数据。 输入的第一行包含一个正整数 $N$。 第二行包含 $N$ 个整数，其中第 $i$ 个整数表示 $A_i$。 第三行包含 $N$ 个整数，其中第 $i$ 个整数表示 $C_i$。

输出格式

程序必须输出到标准输出。 输出应包含一行 $N$ 个整数。第 $k$ 个整数表示如果 Benson 只参观前 $k$ 个区域，且水果分配最优时，他所支付的成本之和的最大值。

数据范围

每个测试用例的最大执行时间为 1.0 秒。对于所有测试用例，输入满足以下限制： $1 \le N \le 400\,000$ $1 \le A_j \le N$ 或 $A_j = -1$ $1 \le C_i \le 10^9$ $C_i \le C_j$ 对于所有 $1 \le i < j \le N$

你的程序将在满足以下限制的输入实例上进行测试：

样例

样例输入 1

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

样例输出 1

1 2 3 4 5

说明 1

我们可以按递增顺序（1, 2, 3, 4, 5）排列水果。Benson 会拿走他经过的所有水果，因此对于每个 $k$ 从 1 到 5，Benson 将拿走 $k$ 个水果，总成本为 $k$。

样例输入 2

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

样例输出 2

3 4 7 9 9

说明 2

如果 Benson 只参观第一个区域，最优方案是将水果 5 放在区域 1，成本为 3。 如果 Benson 只参观前 2 个区域，最优方案是将水果 2 放在区域 1，水果 3 放在区域 2，成本为 $2 + 2 = 4$。 如果 Benson 只参观前 3 个区域，最优方案是将水果 2 放在区域 1，水果 3 放在区域 2，水果 5 放在区域 3，成本为 $2 + 2 + 3 = 7$。 如果 Benson 参观前 4 个或全部 5 个区域，最优方案是将水果按 2, 3, 4, 5, 1 的顺序排列，成本为 $2 + 2 + 2 + 3 = 9$。

样例输入 3

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

样例输出 3

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

样例输入 4

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

样例输出 4

92 173 245 305 305 332 356 367
406 498