A. Color
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Xiao Ming bought a ribbon with $$$n$$$ segments. The $$$i$$$-th segment initially has color $$$c_i$$$. Xiao Ming prefers solid-colored ribbons, so he needs to paint every segment of this ribbon the same color.

For a painting operation $$$(l, r, c)$$$, it means that the interval $$$[l, r]$$$ of the ribbon can be painted with color $$$c$$$ at a cost of $$$w_c + (r - l + 1)$$$, where $$$w_c$$$ is the price of color $$$c$$$.

Now, for each color $$$c = 1, 2, ..., n$$$, please determine the minimum cost for Xiao Ming to paint the entire ribbon into color $$$c$$$.

Input

The first line contains $$$n$$$.

The second line contains $$$n$$$ positive integers, representing $$$c_1, ..., c_n$$$.

The third line contains $$$n$$$ positive integers, representing $$$w_1, ..., w_n$$$.

$$$1 \leq n \leq 2 \times 10^5$$$, $$$1 \leq c_i, w_i \leq n$$$.

Output

Output a single line containing $$$n$$$ numbers, representing the answers for colors $$$1, 2, ..., n$$$.

Examples
Input
4
1 2 2 1
1 10 2 1
Output
3 14 6 5
Input
5
1 3 2 3 5
5 5 5 5 5
Output
9 10 10 10 9