Description

You are given two sequences of positive integers of length $N$, $(A_1, A_2, \ldots, A_N)$ and $(B_1, B_2, \ldots, B_N)$. For $k = 2, 3, \ldots, 2N$, compute the value of $\sum_{i+j \leq k} (A_i + B_j)$, that is, the sum of $(A_i + B_j)$ for all indices $(i, j)$ such that $i + j \leq k$ and $1 \leq i, j \leq N$.

Input Format

The input is given in the following format:

$$\begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_N \\ &B_1 \ B_2 \ \ldots \ B_N \end{aligned}$$

• $1 \leq N \leq 200,000$
• $1 \leq A_i, B_i \leq 10^6$ ($1 \leq i \leq N$)
• All input values are integers.

Output Format

Output $2N - 1$ lines. On the $i$-th line ($1 \leq i \leq 2N - 1$), output the answer for the case where $k = i + 1$.

3
1 1 1
1 1 1

2
6
12
16
18

5
3 7 1 8 3
7 10 5 3 4

10
37
70
114
165
206
230
248
255

1
3
5

8