题目描述
给定正整数 $n$。给出一个 $n\times 2\times 2$ 的 01 数组 $A_{i,j,k}$，其中 $i\in [0,n-1],j\in [0,1],k\in [0,1]$。
定义一种二元运算 $f(x,y)\ (0\le x,y < 2^n,x,y\in \mathbb{Z})$ 的值为：
- 设 $x=\sum_{i=0}^{n-1}2^ia_i$，其中 $a_i\in \{0,1\}$。
- 设 $y=\sum_{i=0}^{n-1}2^ib_i$，其中 $b_i\in \{0,1\}$。
- 设 $z=\sum_{i=0}^{n-1}2^iA_{i,a_i,b_i}$。
- 则 $f(x,y)=z$。
给出两个长为 $2^n$ 的数组 $p,q$（下标均为 $[0,2^n-1]$），计算它们下标做 $f$ 运算的卷积。换句话说，请求出数组 $res$（下标为 $[0,2^n-1]$），其中 $res_i=\sum_{j=0}^{2^n-1}\sum_{k=0}^{2^n-1} [f(j,k)=i]p_iq_j$。
输入格式
第一行一个正整数 $n$。
第二行包含 $n$ 个长度为 $4$ 的 01 串。第 $i$ 个 01 串从前往后表示 $A_{i-1,0,0},A_{i-1,0,1},A_{i-1,1,0},A_{i-1,1,1}$ 的值。
第三行 $2^n$ 个整数，描述数组 $p$。第四行 $2^n$ 个整数，描述数组 $q$。
输出格式
输出一行以空格隔开的 $2^n$ 个整数，描述数组 $res$。
样例数据
样例 1 输入
3
0111 0110 0001
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0样例 1 输出
0 0 0 0 0 0 0 1样例 2 输入
2
1100 1101
2 0 2 1
2 0 2 1样例 2 输出
2 4 3 16样例 3 输入
1
0000
142857142 857142857
998244353 1755646样例 3 输出
999999998000000001 0样例 4
见下发文件中的 ex_conv4.in/ex_conv4.ans。该样例满足子任务 1 的限制。
样例 5
见下发文件中的 ex_conv5.in/ex_conv5.ans。该样例满足子任务 5 的限制。
子任务
请注意，本题的满分为 125 分。
对于所有数据：保证 $n\le 18,0\le p_i\le 10^9,0\le q_i\le 10^9,\sum p_i\le 10^9,\sum q_i\le 10^9$。
- 子任务 1（$1$ 分）$n\le 10$。
- 子任务 2（$1$ 分）每个 01 串都是
0001。 - 子任务 3（$4$ 分）每个 01 串都是
0110。 - 子任务 4（$5$ 分）每个 01 串都是
0001或0111。 - 子任务 5（$114$ 分）无特殊限制。
Hack
Hack 功能在本题中可用。