给定两个序列 $a_0, a_1, \dots, a_n$ 和 $b_0, b_1, \dots, b_n$。你需要计算一个新的序列 $c_0, c_1, \dots, c_n$，使得：

$$c_k = \left( \sum_{i=0}^{k} \binom{k}{i} a_i b_{k-i} \right) \pmod{2^{32}}$$

其中 $\binom{k}{i} = \frac{k!}{i!(k-i)!}$ 为二项式系数。

输出 $c_0, c_1, \dots, c_n$。

输入格式

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

第二行包含 $n + 1$ 个整数 $a_0, a_1, \dots, a_n$ ($0 \le a_i < 2^{32}$)。

第三行包含 $n + 1$ 个整数 $b_0, b_1, \dots, b_n$ ($0 \le b_i < 2^{32}$)。

输出格式

输出一行，包含 $n + 1$ 个整数：$c_0, c_1, \dots, c_n$。

样例

输入 1

5
0 1 2 3 4 5
6 7 8 9 10 11

输出 1

0 6 26 84 240 640