Migrated from Lutece 2675 成神阳太的破防

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

纯音乐，请您欣赏。

——《夏凪ぎ-episode2 piano ver.-》

伊座并，你还我伊座并哼哼啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

病了，是出题人病了（大嘘）

---

诶内个上回说到，成神阳太眼睁睁看着，额……诶内个谁来着，被抓走拆除脑内的量子计算机了（大嘘），心中好生郁闷，终究达到了破防的地步。这一破防，饭不吃了，游戏不打了，甚至青年大学习都不做了，废人一个。

终究大作业还是要写的，不做青年大学习但是写大作业的成神阳太是屑鉴二象性的。这次计算机组成原理大作业是要自己设计一个 ALU，也就是算术逻辑单元。正常的 ALU 支持各种各样的运算，比如算术加法，按位异或，二进制移位等等，不过老师终究肯定还是按报告长度给分的，功能越多，报告越长，给分越高，很合理。

但是成神阳太破防了，贴吧蛆宝一致认为他是个沙口，所以他 ALU 是瞎设计的，Verilog 也是瞎写的，报告也是抄的，拿了个平均分走了，留下了一堆垃圾文档，此可谓被破防人碰过的东西，没有一样是无辜的。

1145141919810 秒之后，他的垃圾文档被某外星高级智慧生命获得，我们简称为三体人。这个三体人十分喜欢计算机，前面这个秒数也是他用高级计算机分析各种数据推算出来的，事实证明他的推算分毫不差。这个三体人希望研究古老人类是怎么搭建初等计算机的，他看到了成神阳太在破防的时候写的垃圾文档，他也破防了，正所谓被破防人碰过的东西，没有一样是无辜的。

成神阳太做了一个 $n$ 位二进制运算器，每一位的运算规则是确定的，具体来说，从低到高第 $i\ (0\le i<n)$ 位的运算规则可以用 $P_i(x,y)$ 表示，其中 $x,y$ 均为一个二进制位（bit），$P_i(x,y)$ 的结果也是一个二进制位（bit）。这个三体人本来是想知道他写的 Verilog 对不对，所以生成了很多 $[0,2^n)$ 之间的整数用来测试。具体来说，他生成了一些 $[0,2^n)$ 之间的整数，并把它们分成 $A,B$ 两组。他想知道 $A$ 组的任意一个数和 $B$ 组的任意一个数经过这个二进制运算器之后得到的结果是多少。可以知道，结果也是在 $[0,2^n)$ 范围内的一个整数。由于数量太多，他只想知道对于结果的多重集合，每个 $[0,2^n)$ 之间的整数在集合中出现多少次就可以了。

因为这个三体人破防了，所以他打开了《成神之日》喝两瓶啤酒，吃一碗拉面了，在破防的时候仍要坚持破防的三体人是屑。而生成结果这个活，就由你来干了。

如果不知道 ALU 是什么，或者没有系统学习过计算机组成原理（或相关课程）的话，请跳转到 Note 部分。

Input

第一行一个正整数 $n$，表示这个 ALU 的位数。

第二行有 $n$ 个长度为 $4$ 的 $01$ 字符串，第 $i$ 个字符串表示 $P_{i-1}(x,y)$ 的规则，每个字符串从左到右均分别表示 $P_{i-1}(\texttt 0,\texttt 0),P_{i-1}(\texttt 0,\texttt 1),P_{i-1}(\texttt 1,\texttt 0),P_{i-1}(\texttt 1,\texttt 1)$ 的结果。

第三行 $2^n$ 个整数 $a_0,a_1,\ldots ,a_{2^n-1}$，第 $i$ 个数表示 $A$ 组中整数 $i-1$ 的个数。

第四行 $2^n$ 个整数 $b_0,b_1,\ldots ,b_{2^n-1}$，第 $i$ 个数表示 $B$ 组中整数 $i-1$ 的个数。

Output

输出一行 $2^n$ 个整数，第 $i$ 个整数表示对于所有 $a\in A,b\in B$，$a$ 和 $b$ 经过 ALU 运算后的结果为 $i-1$ 的个数。

Samples

2
0001 0111
1 1 4 5
1 4 1 9

6 4 81 74

1
0000
114 514
1919 810

1713812 0

Constraints

$1\le n\le 18,a_i,b_i\ge 0,\sum a_i,\sum b_i\le 10^9$，保证所有 $P_i(x,y)$ 字符串长度均为 $4$ 且只包含 $\texttt 0, \texttt 1$ 两种字符。

Note

这个部分是关于计算机组成原理，CPU 和 ALU 的简单介绍。至于 Verilog，它是一个硬件描述语言，可以理解为写 Verilog 可以模拟真正的硬件之间的交互，出题人也没咋学过 Verilog，并且本题跟 Verilog 没啥关系，从略。

（给非专业学生出专业问题的出题人是大屑，所以下面是计组不严谨的补课时间）

ALU，即算术运算单元，是 CPU 的重要组成部分之一，另一个是寄存器（Register）。我们可以利用寄存器组和 ALU 的串联简单实现一个 CPU。但是真正的 CPU 并非寄存器和 ALU 的串联。

如果不熟悉硬件的话，这道题里可以将 ALU 抽象成一个函数 $f(a,b)$，其中 $a$ 和 $b$ 都是一个整数，在运算时，均采用二进制方式运算，对于运算结果 $r$，相当于 $r_i=P_i(a_i,b_i)$，其中 $r_i,a_i,b_i$ 分别表示对应整数二进制的第 $i$ 位（从低到高）。

复杂一点说，那还是去系统学习计算机组成原理好，推荐南京大学的计算机组成原理和操作系统课程。B 站搜不是事。

Resources

2021 UESTC ICPC Training for Math and Geometry