You work at a supermarket.

There are $n$ fruits in the supermarket. The $i$-th fruit has a deliciousness of $i$ and a price of $c_i$. It is guaranteed that $c_i$ is non-decreasing.

You need to arrange these $n$ fruits in a row on a shelf. The fruit at the $j$-th position is $a_j$. However, you have not decided on the order yet, so some $a_j$ may be $-1$, indicating that the fruit at that position is not yet determined.

After you decide on the arrangement, a customer enters to buy fruits. They walk from the first position to the end, and whenever they encounter a fruit with a deliciousness higher than any fruit seen so far, they buy it. The customer leaves after inspecting the $k$-th position.

You want to choose an optimal arrangement to maximize the total money the customer spends.

Since you do not know the value of $k$, you want to find the answer for every $k$ from $1$ to $n$. You may choose different arrangements for different values of $k$.

Input

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

The third line contains $n$ positive integers $c_1, c_2, \dots, c_n$.

Output

Output a single line containing $n$ positive integers, representing the answers for $k=1, 2, \dots, n$.

Examples

Input 1

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

Output 1

3 4 7 9 9

Note 1

• For $k=1$, the optimal strategy is to place the 5th fruit in the first position, i.e., $a_1=5$, with the rest arbitrary.
• For $k=2$, the optimal strategy is to set $a_1=2$.
• For $k=3$, the optimal strategy is to set $a_1=2, a_3=5$.
• For $k=4$, the optimal strategy is to set $a_1=2, a_3=4, a_4=5$.
• For $k=5$, the optimal strategy is to set $a_1=2, a_3=4, a_4=5, a_5=1$.

Input 2

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 2

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

Input 3

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

Output 3

92 173 245 305 305 332 356 367 406 498

Constraints

This problem uses bundled subtasks.

For all data, it is guaranteed that $1 \le n \le 4 \times 10^5$, $-1 \le a_i \le n$, $a_i \neq 0$, $1 \le c_i \le 10^9$, there are no two identical positive integers in $a$, and $c$ is non-decreasing.