小C非常喜欢数字《3》。他喜欢与它有关的一切。
现在他对以下问题感兴趣:
有两个 $$$2^n$$$ 整数数组 $$$a_0,a_1,...,a_{2^n-1}$$$ 和 $$$b_0,b_1,...,b_{2^n-1}$$$。
任务是对每个$$$i (0 \leq i \leq 2^n-1)$$$,计算$$$c_i=\sum a_j \cdot b_k$$$ ($$$j|k=i$$$ 和$$$j\&k=0$$$,其中“$$$|$$$”表示按位或运算,“$$$\&$$$”表示按位与运算)。
令人惊讶的是,可以证明确实存在 $$$3^n$$$ 三元组 $$$(i,j,k)$$$,使得 $$$j|k=i$$$、$$$j\&k=0$$$ 和 $$$0 \leq i,j,k \leq 2^n-1$$$。所以小C想要出色地解决这个优秀的问题(因为它与$$$3$$$有很好的关系)。
帮他计算所有$$$c_i$$$。小C非常喜欢$$$3$$$,所以他只想知道每一个$$$c_i \& 3$$$。
输入
第一行包含一个整数 $$$n (0 \leq n \leq 21)$$$。
第二行在 $$$[0,3]$$$ 中包含 $$$2^n$$$ 整数,不带空格 — 其中第 $$$i$$$ 是 $$$a_{i-1}$$$。
第三行在 $$$[0,3]$$$ 中包含 $$$2^n$$$ 整数,不带空格 — 其中第 $$$i$$$ 是 $$$b_{i-1}$$$。
输出
打印一行包含 $$$[0,3]$$$ 中的 $$$2^n$$$ 整数,不带空格 — 其中第 $$$i$$$ 是 $$$c_{i-1}\&3$$$。 (很明显$$$c_{i}\&3$$$在$$$[0,3]$$$中)。
示例
输入 #1
1 11 11
输出 #1
12
输入 #2
2 0123 3210
输出 #2
0322