Building fence - MarisaOJ: Marisa Online Judge

Marisa has

n

$n$ pieces of wood and wants to use them to make a fence. The

i

$i$ -th piece of wood has a beauty value of either

A_{i}

$A_i$ or

B_{i}

$B_i$ . If Marisa chooses

k

$k$ pieces of wood to make a fence around her house, she will choose

k - 1

$k-1$ pieces to build the fence and

1

$1$ piece to make the gate. In this case, the pieces used for the fence will have a beauty value of

A_{i}

$A_i$ , and the piece used for the gate will have a beauty value of

B_{i}

$B_i$ . For each value of

k

$k$ from

1

$1$ to

n

$n$ , help Marisa calculate the maximum beauty value she can achieve. ### Input - The first line contains an integer

n

$n$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The third line contains

n

$n$ integers

B_{i}

$B_i$ . ### Output - Output

n

$n$ integers, where the

i

$i$ -th integer represents the maximum beauty value when Marisa uses

i

$i$ pieces of wood. ### Constraints -

1 \leq n \leq 10^{5}

$1 \le n \le 10^5$ . -

1 \leq A_{i}, B_{i} \leq 10^{9}

$1 \le A_i, B_i \le 10^9$ . ### Example Input:

21221

$2 1 2 2 1$

Output:

24

$2 4$

Topic

Sorting

Greedy

Rating

1200

Solution (1)

Solution