说明

给定两个长度为 $N$ 的正整数序列 $(A_1, A_2, \ldots, A_N)$ 和 $(B_1, B_2, \ldots, B_N)$。对于 $k = 2, 3, \ldots, 2N$，计算 $\sum_{i+j \leq k} (A_i + B_j)$ 的值，即对所有满足 $i + j \leq k$ 且 $1 \leq i, j \leq N$ 的下标对 $(i, j)$ 求 $(A_i + B_j)$ 的和。

输入格式

输入以如下格式给出：

$$\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$）
• 所有输入值均为整数。

输出格式

输出 $2N - 1$ 行。在第 $i$ 行（$1 \leq i \leq 2N - 1$）输出当 $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