题目描述

给定正整数 $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 功能在本题中可用。