给定一个整数 $n$ 和两个整数序列 $a_0, a_1, \dots, a_{n-1}$ 以及 $b_0, b_1, \dots, b_{n-1}$，你需要计算一个整数序列 $c_0, c_1, \dots, c_{n-1}$，定义如下：

$$c_k = \sum_{i+j \equiv k \pmod n} a_i b_j$$

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。 第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$ ($-10^6 \le a_i \le 10^6$)。 第三行包含 $n$ 个整数 $b_0, b_1, \dots, b_{n-1}$ ($-10^6 \le b_i \le 10^6$)。

输出格式

在一行中输出 $n$ 个整数 $c_0, c_1, \dots, c_{n-1}$。

样例

样例输入 1

3
1 1 4
5 1 4

样例输出 1

13 22 25

说明

对于样例：

$c_0 = a_0b_0 + a_1b_2 + a_2b_1 = 1 \times 5 + 1 \times 4 + 4 \times 1 = 13$

$c_1 = a_0b_1 + a_1b_0 + a_2b_2 = 1 \times 1 + 1 \times 5 + 4 \times 4 = 22$

$c_2 = a_0b_2 + a_1b_1 + a_2b_0 = 1 \times 4 + 1 \times 1 + 4 \times 5 = 25$