给你两个长度为 $n$ 的正整数序列：$(a_1, a_2, \dots, a_n)$ 和 $(b_1, b_2, \dots, b_n)$。

对于 $k = 2, 3, \dots, 2n$，计算以下式子的值：

$$\sum_{i+j \le k} (a_i + b_j)$$

即所有满足 $i + j \le k$ 且 $1 \le i, j \le n$ 的下标对 $(i, j)$ 的 $(a_i + b_j)$ 之和。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数：依次为序列 $a$ 的元素 ($1 \le a_i \le 10^6$)。

第三行包含 $n$ 个整数：依次为序列 $b$ 的元素 ($1 \le b_i \le 10^6$)。

输出格式

输出 $2n - 1$ 行。在第 $i$ 行中，输出 $k = i + 1$ 时的答案。

样例

输入样例 1

3
1 1 1
1 1 1

输出样例 1

2
6
12
16
18

输入样例 2

5
3 7 1 8 3
7 10 5 3 4

输出样例 2

10
37
70
114
165
206
230
248
255

输入样例 3

1
3
5

输出样例 3

8