题目描述

对于多项式乘法，，我们可以利用快速傅里叶变换(Fast Fourier Transform)在$O(nlogn)$的时间复杂度内快速解决。

现在神犇ccz提出了一种新的多项式运算$\bigotimes$。

$F(x) = \sum_{i=0}^{n-1}f_{i}x^{i}$

$G(x) = \sum_{i=0}^{n-1}g_{i}x^{i}$

$H(x) = \sum_{i=0}^{n-1}h_{i}x^{i}$

$h_{m} = \bigotimes_{i=0}^{m}f_{i} \bigotimes g_{m-i}$

其中$\bigotimes$表示异或运算，即C或C++中的^运算，并相应的提出了一种快速异或变换(Fast Xor Transform)来快速进行这种新的运算。

下面告诉你两个多项式$F(x)$,$G(x)$，请你实现快速异或变换并输出$H(x)$。

输入格式

第一行是一个整数$n$。

接下来一行$n$个整数，第$i$个表示$f_{i-1}$。

接下来一行$n$个整数，第$i$个表示$g_{i-1}$。

输出格式

一行$n$个整数，第$i$个表示$h_{i-1}$。

样例

ex_fxt1.in

5
1 9 2 6 8
1 7 105 110 102

ex_fxt1.ans

0 14 101 13 99

样例解释

异或运算(C/C++的^运算)规则如下：

设$A,B$为两个$32$位无符号整数，$A,B$的二进制表示从低位到高位分别为$a_{1} \dots a_{32}$,$b_{1} \dots b_{32}$，设$A \bigotimes B=C$，$C$二进制表示从低位到高位分别为$c_{1} \dots c_{32}$，则$c_{i} = (a_{i}!=b_{i})$，即若$A,B$的第$i$不同，则$C$的第$i$位为$1$，否则为$0$。

例如：

$9$的二进制表示为

$00000000000000000000000000001001$

$7$的二进制表示为

$00000000000000000000000000000111$

$9 \bigotimes 7$的二进制表示为

$00000000000000000000000000001110$

即$14$。

该样例中，$h_{0}=f_{0} \bigotimes g_{0}=0$，$h_{1}=(f_{0} \bigotimes g_{1}) \bigotimes (f_{1} \bigotimes g_{0})=14$，$h_{2}=(f_{0} \bigotimes g_{2}) \bigotimes (f_{1} \bigotimes g_{1}) \bigotimes (f_{2} \bigotimes g_{0})=101$，余下的同理。

数据范围

对于$60\%$的数据，$n \leq 1000$

对于$100\%$的数据，$1 \leq n \leq 100000$，$0 \leq a_i,b_i \leq 10^{9}$