宇宙的卷积

题目信息

时间限制: 3s

空间限制: 512M

输入文件: juanji.in

输出文件: juanji.out

题目描述

B 宇宙中的卷积定义如下：

其中 $\vee$ 表示按位或。

快速计算卷积结果是 B 宇宙中每个程序员的入门课（相当于 Earth 宇宙的 Hello World）。

x 年 y 月 z 日，Earth 宇宙的 A 公司突然大裁员，u 失去了工作，不得已润出 Earth 宇宙来到 B 宇宙。u 除了写代码啥也不会，只好通过求解长度为 $N=2^n$ 的两个序列 $a_0, a_1, \dots, a_{N-1}$ 和 $b_0, b_1, \dots, b_{N-1}$ 的卷积来考取 B 宇宙的程序员资格证啦！

输入格式

第一行一个数 $n$。

第二行 $N$ 个数 $a_0, a_1, \dots, a_{N-1}$。

第三行 $N$ 个数 $b_0, b_1, \dots, b_{N-1}$。

输出格式

一行 $N$ 个数 $c_0, c_1, \dots, c_{N-1}$。

样例

样例输入

3
12 37 33 80 52 46 56 28
80 16 43 57 86 94 18 50

样例输出

92 117 113 160 138 146 142 174

数据范围与提示

对于所有数据，$1\leq a_i, b_i\leq 10^9$。