B. Bracket Problem Yet Again
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A balanced bracket string is a string consisting of '(' and ')', which can make a valid mathematical expression by inserting $$$0$$$ or $$$+$$$ in the string $$$0$$$ or more times.

Bob had learned how to find the balanced bracket string with minimum cost, when the cost is defined as follows.

  • If position $$$i$$$ contains '(', the cost of the position is $$$a_i$$$;
  • If position $$$i$$$ contains ')', the cost of the position is $$$b_i$$$;
  • The cost of a balanced bracket string is the sum of costs of all positions.

While rethinking about the solution, Bob became curious about the following problem.

  • Assuming I can make $$$a_i$$$ and $$$b_i$$$ both $$$0$$$ for at most $$$k$$$ different indices, what is the new minimum cost?

As he was unable to solve the modified problem, he asked you to solve it. As Bob is a very selfish person, he wants you to solve it for each possible value of $$$k$$$. The indices chosen for $$$k=x$$$ need not be a strict subset of the indices chosen for $$$k=x+1$$$. In other words, the problem must be solved independently for all values of $$$k$$$.

Input

The first line contains an even integer $$$n$$$, the length of the bracket sequence. ($$$2 \le n \le 2\cdot 10^5$$$)

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$, the costs of using '(' on each index. ($$$0 \le a_i \le 10^9$$$)

The third line contains $$$n$$$ integers $$$b_1,b_2,\cdots,b_n$$$, the costs of using ')' on each index. ($$$0 \le b_i \le 10^9$$$)

Output

Output $$$n+1$$$ integers $$$c_0,c_1,\cdots,c_n$$$ separated by spaces. $$$c_x$$$ is defined by the minimum cost of the problem when $$$k=x$$$.

Example
Input
4
0 5 0 5
3 3 3 3
Output
6 3 0 0 0